← 返回题目列表

AtCoder · wtf19_b

B. 九的倍数

中文机器翻译题面 查看原题

分数: 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