配点 : $1400$ 点

問題文

以下の条件を満たす文字列 $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$ を表します。

制約

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

入力

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

$N$

$Q$

$l_1$ $r_1$

$:$

$l_Q$ $r_Q$

出力

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

4
2
1 2
2 4

136

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

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