정수와 구간

시간 제한은 3000 ms, 메모리 제한은 512 MB이다.

Isaac에게는 앞자리에 0이 올 수 있는 십진수 정수 $\overline{a_1 a_2 \dots a_n}$가 있다. $m$개의 구간 $[l_1, r_1], [l_2, r_2], \dots, [l_m, r_m]$이 주어지며, 각 구간 $i$에 대해 $a_{l_i} \times a_{l_i + 1} \times \dots \times a_{r_i} \bmod 9 = 0$이 성립한다고 한다. 이 조건을 모두 만족하는 정수 $\overline{a_1 a_2 \dots a_n}$의 개수를 $(10^9+7)$로 나눈 나머지를 구하라.

입력은 여러 개의 테스트 케이스로 이루어져 있으며, 파일의 끝(EOF)에서 끝난다.

각 테스트 케이스의 첫 줄에는 두 정수 $n$과 $m$이 주어진다. 이어지는 $m$개의 줄에는 각각 두 정수 $l_i$와 $r_i$가 주어진다.

각 테스트 케이스마다 결과를 나타내는 정수를 한 줄에 출력한다.

• $1 \leq n, m \leq 10^3$
• $1 \leq l_i \leq r_i \leq n$
• 테스트 케이스는 최대 $100$개이다.