1072 : Modulo Nine

Description

Bobo has a decimal integer $\overline{a_1 a_2 \dots a_n}$, possibly with leading zeros. He knows that for m ranges [l₁,r₁], [l₂,r₂], …, [l_m,r_m], it holds that a_li × a_li + 1 × … × a_ri mod  9 = 0. Find the number of valid integers $\overline{a_1 a_2 \dots a_n}$, modulo (10⁹+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 l_i and r_i.

• 1 ≤ n, m ≤ 50
• 1 ≤ l_i ≤ r_i ≤ n
• There are at most 100 test cases.

Output

For each test case, print an integer which denotes the result.

Sample

2 1
1 2
4 2
1 3
2 4
50 1
1 50

40
4528
100268660

Hint

Source

Author

ftiasch