Bobo는 선행 0이 있을 수도 있는 십진 정수 $\overline{a_1 a_2 \dots a_n}$을 가지고 있다. 그는 $m$개의 구간 $[l_1, r_1], [l_2, r_2], \dots, [l_m, r_m]$에 대해 $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)$로 나눈 나머지를 출력하라.

입력

입력은 여러 테스트 케이스로 이루어지며 파일 끝에서 종료된다.

각 테스트 케이스의 첫째 줄에는 두 정수 $n$과 $m$이 주어진다.

다음 $m$개 줄 중 $i$번째 줄에는 두 정수 $l_i$와 $r_i$가 주어진다.

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

출력

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

예제

입력 1

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

출력 1

40
4528
100268660