{"problem":{"name":"Multiple of Nine","description":{"content":"Count the number of strings $S$ that satisfy the following constraints, modulo $10^9 + 7$. *   The length of $S$ is exactly $N$. *   $S$ consists of digits (`0`...`9`). *   You are given $Q$ interval","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"wtf19_b"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 10^9$\n*   $1 \\leq Q \\leq 15$\n*   $1 \\leq l_i \\leq r_i \\leq N$\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"wtf19_b","tags":[],"sample_group":[["4\n2\n1 2\n2 4","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$."],["6\n3\n2 5\n3 5\n1 3","2720"],["20\n10\n2 15\n5 6\n1 12\n7 9\n2 17\n5 15\n2 4\n16 17\n2 12\n8 17","862268030"]],"created_at":"2026-03-03 11:01:13"}}