Modulo Nine

题号：NC53383
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
Special Judge, 64bit IO Format: %lld

题目描述

Bobo has a decimal integer $\overline{a_1 a_2 \dots a_n}$ , possibly with leading zeros. 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 ith of the following m lines contains two integers  and .

* 
* 
* There are at most 100 test cases.

输出描述:

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

示例1

输入

复制

输出

复制

40
4528
100268660