CF95D.Horse Races

Petya likes horse racing very much. Horses numbered from l to r take part in the races. Petya wants to evaluate the probability of victory; for some reason, to do that he needs to know the amount of nearly lucky horses' numbers. A nearly lucky number is an integer number that has at least two lucky digits the distance between which does not exceed k. Petya learned from some of his mates from Lviv that lucky digits are digits 4 and 7. The distance between the digits is the absolute difference between their positions in the number of a horse. For example, if k = 2, then numbers 412395497, 404, 4070400000070004007 are nearly lucky and numbers 4, 4123954997, 4007000040070004007 are not.

Petya prepared t intervals [l__i, r__i] and invented number k, common for all of them. Your task is to find how many nearly happy numbers there are in each of these segments. Since the answers can be quite large, output them modulo 1000000007 (109 + 7).

佩佳非常喜欢赛马。编号从 $l$ 到 $r$ 的马参加比赛。佩佳希望评估获胜概率；出于某种原因，他需要知道这些马编号中“近似幸运数”的个数。一个“近似幸运数”是指一个整数，其十进制表示中至少包含两个幸运数字，且这两个幸运数字在该数中的位置距离不超过 $k$。佩佳从他在利沃夫的一些朋友那里得知，幸运数字是 $4$ 和 $7$。两个数字之间的距离定义为它们在该数中位置（从左往右，从 $1$ 开始计数）的绝对差值。例如，当 $k = 2$ 时，数 $412395497$、$404$、$4070400000070004007$ 是近似幸运数，而 $4$、$4123954997$、$4007000040070004007$ 则不是。

佩佳准备了 $t$ 个区间 $[l_i,\, r_i]$，并对所有这些区间使用同一个给定的数 $k$。你的任务是：对每个区间，求出其中近似幸运数的个数。由于答案可能非常大，请将结果对 $1000000007$（即 $10^9 + 7$）取模后输出。

The first line contains two integers t and k (1 ≤ t, k ≤ 1000) — the number of segments and the distance between the numbers correspondingly. Next t lines contain pairs of integers l__i and r__i (1 ≤ l ≤ r ≤ 101000). All numbers are given without the leading zeroes. Numbers in each line are separated by exactly one space character.

第一行包含两个整数 $t$ 和 $k$（$1 \leq t, k \leq 1000$）—— 分别表示线段的数量以及数字之间的距离。接下来的 $t$ 行每行包含一对整数 $l_i$ 和 $r_i$（$1 \leq l \leq r \leq 10^{1000}$）。所有数字均不带前导零。每行中的数字之间恰好由一个空格字符分隔。

Output t lines. In each line print one integer — the answer for the corresponding segment modulo 1000000007 (109 + 7).

输出 t 行。每行输出一个整数——对应区间的答案对 1000000007（即 $10^9 + 7$）取模的结果。

In the first sample, the four nearly lucky numbers are 44, 47, 74, 77.

In the second sample, only 74 and 77 are in the given segment.

在第一个样例中，四个“近似幸运数”是 44、47、74、77。

在第二个样例中，给定区间内仅有 74 和 77。