Integers and Ranges

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.

• $1 \leq n, m \leq 10^3$
• $1 \leq l\_i \leq r\_i \leq n$
• There are at most $100$ test cases.