Isaac 有一个十进制整数 $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} \equiv 0 \pmod 9$。求满足条件的整数 $a_1 a_2 \dots a_n$ 的个数，结果对 $(10^9 + 7)$ 取模。

输入格式

输入包含多组测试数据，以文件结束符（EOF）结束。 每组测试数据的第一行包含两个整数 $n$ 和 $m$。 接下来的 $m$ 行中，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$。

• $1 \le n, m \le 10^3$
• $1 \le l_i \le r_i \le n$
• 最多有 100 组测试数据。

输出格式

对于每组测试数据，输出一个整数，表示结果。

样例

样例输入 1

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

样例输出 1

40
4528
100268660