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