B - Multiple of Nine Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

Score : 1400 points

Problem Statement

Count the number of strings S that satisfy the following constraints, modulo 10^9 + 7.

  • The length of S is exactly N.
  • S consists of digits (0...9).
  • You are given Q intervals. For each i (1 \leq i \leq Q), the integer represented by S[l_i \ldots r_i] (the substring of S between the l_i-th (1-based) character and the r_i-th character, inclusive) must be a multiple of 9.

Here, the string S and its substrings may have leading zeroes. For example, 002019 represents the integer 2019.

Constraints

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

Input

Input is given from Standard Input in the following format:

N
Q
l_1 r_1
:
l_Q r_Q

Output

Print the number of strings that satisfy the conditions, modulo 10^9 + 7.

Sample Input 1

4
2
1 2
2 4

Sample Output 1

136

For example, S = 9072 satisfies the conditions because both S[1 \ldots 2] = 90 and S[2 \ldots 4] = 072 represent multiples of 9.

Sample Input 2

6
3
2 5
3 5
1 3

Sample Output 2

2720

Sample Input 3

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

Sample Output 3

862268030

配点 : 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 で割った余りを出力せよ。

入力例 1

4
2
1 2
2 4

出力例 1

136

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

入力例 2

6
3
2 5
3 5
1 3

出力例 2

2720

入力例 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