← 返回题目列表

Codeforces · 95/D

D. 赛马

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

Petya非常喜欢赛马。编号从 l 到 r 的马匹参加比赛。彼佳想要评估胜利的可能性;出于某种原因,要做到这一点,他需要知道几乎幸运的马匹的数量。近幸运数是至少有两个幸运数字且其之间的距离不超过 k 的整数。佩蒂亚从利沃夫的一些朋友那里得知,幸运数字是数字4和7。数字之间的距离是它们在马数中的位置之间的绝对差。例如,如果 k = 2,则数字 412395497、404、4070400000070004007 几乎是幸运的,而数字 4、4123954997、4007000040070004007 则不是。

Petya 准备了 t 区间 [li, ri] 并发明了数字 k,它们都是通用的。你的任务是找出每个部分中有多少个接近快乐的数字。由于答案可能相当大,因此输出它们对 1000000007 (109 + 7) 取模。

输入

第一行包含两个整数 t 和 k (1 ≤ t, k ≤ 1000) — 线段的数量以及相应数字之间的距离。接下来的 t 行包含整数对 li 和 ri (1 ≤ l ≤ r ≤ 101000)。所有数字均不带前导零。每行中的数字均由一个空格字符分隔。

输出

输出 t 行。在每一行中打印一个整数——相应段的答案模 1000000007 (109 + 7)。

示例

输入 #1

1 2
1 100

输出 #1

4

输入 #2

1 2
70 77

输出 #2

2

输入 #3

2 1
1 20
80 100

输出 #3

0
0

注意

在第一个样本中,四个接近幸运的数字是 44、47、74、77。

在第二个示例中,给定段中只有 74 和 77。