1072 : Modulo Nine
Time Limit: 5 Sec Memory Limit: 512 Mb Submitted: 7 Solved: 3Description
Bobo has a decimal integer $\overline{a_1 a_2 \dots a_n}$, possibly with leading zeros. He knows that for m ranges [l1,r1], [l2,r2], …, [lm,rm], it holds that ali × ali + 1 × … × ari mod 9 = 0. Find the number of valid integers $\overline{a_1 a_2 \dots a_n}$, modulo (109+7).
Input
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 ith of the following m lines contains two integers li and ri.
- 1 ≤ n, m ≤ 50
- 1 ≤ li ≤ ri ≤ n
- There are at most 100 test cases.
Output
For each test case, print an integer which denotes the result.
Sample Input
2 1 1 2 4 2 1 3 2 4 50 1 1 50
Sample Output
40 4528 100268660
Hint
Author
ftiasch