시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 9 | 7 | 6 | 75.000% |
Isaac has a decimal integer $\overline{a_1 a_2 \dots a_n}$, possibly with leading zeroes. He knows that for $m$ ranges $[l_1, r_1], [l_2, r_2], \dots, [l_m, r_m]$, it holds that $a_{l_i} \times a_{l_i + 1} \times \dots \times a_{r_i} \bmod 9 = 0$. Find the number of valid integers $\overline{a_1 a_2 \dots a_n}$, modulo $(10^9+7)$.
The input consists of several test cases and is terminated by end-of-file.
The first line of each test case contains two integers $n$ and $m$.
The $i$th of the following $m$ lines contains two integers $l_i$ and $r_i$.
For each test case, print an integer which denotes the result.
2 1 1 2 4 2 1 3 2 4 50 1 1 50
40 4528 100268660