分数: 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-th (1基的)字符到第 r_i个字符,包括两端)表示的整数必须是 9.
的倍数。此处,字符串 S 及其子字符串可能有前导零。
例如, 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