Score : 1400 points
Count the number of strings S that satisfy the following constraints, modulo 10^9 + 7.
0
...9
).Here, the string S and its substrings may have leading zeroes.
For example, 002019
represents the integer 2019.
Input is given from Standard Input in the following format:
N Q l_1 r_1 : l_Q r_Q
Print the number of strings that satisfy the conditions, modulo 10^9 + 7.
4 2 1 2 2 4
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.
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