题目描述

以下の条件を満たす文字列 $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$ 文字目 (先頭を $1$ 文字目とする) から $r_i$ 文字目まで (両端含む) の部分文字列) が表す整数は $9$ の倍数でなければならない。

ここで、文字列 $S$ やその部分文字列が $0$ から始まっても構いません。 例えば、002019 は整数 $2019$ を表します。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

条件を満たす文字列の個数を $10^9\ +\ 7$ で割った余りを出力せよ。

题目大意

对满足以下条件的整数序列 $S$ 计数：

• 长度为 $N$。
• $S_i\in[0,9]$
• 满足 $Q$ 条限制：$\left(\sum_{j=l_i}^{r_i}a_j\right)\bmod 9 = 0$

对 $10^9+7$ 取模。

$N\le 10^9,Q\le 15$。

4
2
1 2
2 4

136

6
3
2 5
3 5
1 3

2720

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

862268030

提示

制約

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

Sample Explanation 1

例えば、$S\ =$9072 は条件を満たします。なぜなら、$S[1\ \ldots\ 2]\ =$90 と $S[2\ \ldots\ 4]\ =$072 がいずれも $9$ の倍数であるためです。