{"raw_statement":[{"iden":"problem statement","content":"Count the number of strings $S$ that satisfy the following constraints, modulo $10^9 + 7$.\n\n*   The length of $S$ is exactly $N$.\n*   $S$ consists of digits (`0`...`9`).\n*   You are given $Q$ intervals. For each $i (1 \\leq i \\leq Q)$, the integer represented by $S[l_i \\ldots r_i]$ (the substring of $S$ between the $l_i$\\-th ($1$\\-based) character and the $r_i$\\-th character, inclusive) must be a multiple of $9$.\n\nHere, the string $S$ and its substrings may have leading zeroes. For example, `002019` represents the integer $2019$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 10^9$\n*   $1 \\leq Q \\leq 15$\n*   $1 \\leq l_i \\leq r_i \\leq N$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$Q$\n$l_1$ $r_1$\n$:$\n$l_Q$ $r_Q$"},{"iden":"sample input 1","content":"4\n2\n1 2\n2 4"},{"iden":"sample output 1","content":"136\n\nFor example, $S = $ `9072` satisfies the conditions because both $S[1 \\ldots 2] = $ `90` and $S[2 \\ldots 4] = $ `072` represent multiples of $9$."},{"iden":"sample input 2","content":"6\n3\n2 5\n3 5\n1 3"},{"iden":"sample output 2","content":"2720"},{"iden":"sample input 3","content":"20\n10\n2 15\n5 6\n1 12\n7 9\n2 17\n5 15\n2 4\n16 17\n2 12\n8 17"},{"iden":"sample output 3","content":"862268030"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}