题目描述

请计算满足以下条件的字符串 $S$ 的个数，并将结果对 $10^9+7$ 取模。

• $S$ 的长度恰好为 $N$。
• $S$ 仅由数字（0 到 9）组成。
• 给定 $Q$ 个区间。对于每个 $i\ (1 \leq i \leq Q)$，要求 $S[l_i \ldots r_i]$（即 $S$ 的第 $l_i$ 个字符到第 $r_i$ 个字符，包含两端）所表示的整数必须是 $9$ 的倍数。

这里，字符串 $S$ 及其子串可以以 $0$ 开头。例如，002019 表示整数 $2019$。

输入格式

输入按以下格式从标准输入读入。

$N$ $Q$ $l_1$ $r_1$ $:$ $l_Q$ $r_Q$

输出格式

输出满足条件的字符串个数，对 $10^9+7$ 取模。

输入输出样例 #1

输入 #1

4
2
1 2
2 4

输出 #1

136

输入输出样例 #2

输入 #2

6
3
2 5
3 5
1 3

输出 #2

2720

输入输出样例 #3

输入 #3

20
10
2 15
5 6
1 12
7 9
2 17
5 15
2 4
16 17
2 12
8 17

输出 #3

862268030

说明/提示

限制条件

• $1 \leq N \leq 10^9$
• $1 \leq Q \leq 15$
• $1 \leq l_i \leq r_i \leq N$

样例解释 1

例如，$S =$9072 满足条件。因为 $S[1 \ldots 2] =$90 和 $S[2 \ldots 4] =$072 都是 $9$ 的倍数。