{"raw_statement":[{"iden":"statement","content":"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.\n\nPetya 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)."},{"iden":"input","content":"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."},{"iden":"output","content":"Output _t_ lines. In each line print one integer — the answer for the corresponding segment modulo 1000000007 (109 + 7)."},{"iden":"examples","content":"Input\n\n1 2\n1 100\n\nOutput\n\n4\n\nInput\n\n1 2\n70 77\n\nOutput\n\n2\n\nInput\n\n2 1\n1 20\n80 100\n\nOutput\n\n0\n0"},{"iden":"note","content":"In the first sample, the four nearly lucky numbers are 44, 47, 74, 77.\n\nIn the second sample, only 74 and 77 are in the given segment."}],"translated_statement":[{"iden":"statement","content":"Petya 非常喜欢赛马。编号从 #cf_span[l] 到 #cf_span[r] 的马参加比赛。Petya 希望评估获胜概率；出于某种原因，他需要知道“近幸运数”的数量。一个 #cf_span(class=[tex-font-style-underline], body=[近幸运]) 数是指至少包含两个幸运数字，且这两个数字之间的距离不超过 #cf_span[k] 的整数。Petya 从他在利沃夫的朋友们那里得知，幸运数字是数字 #cf_span[4] 和 #cf_span[7]。数字之间的距离是指它们在马编号中的位置的绝对差值。例如，如果 #cf_span[k = 2]，则数字 #cf_span[412395497]、#cf_span[404]、#cf_span[4070400000070004007] 是近幸运数，而数字 #cf_span[4]、#cf_span[4123954997]、#cf_span[4007000040070004007] 不是。\n\nPetya 准备了 #cf_span[t] 个区间 #cf_span[[li, ri]]，并为所有区间发明了一个公共的数字 #cf_span[k]。你的任务是找出每个区间中近幸运数的个数。由于答案可能很大，请对 #cf_span[1000000007]（#cf_span[109 + 7]）取模输出。\n\n第一行包含两个整数 #cf_span[t] 和 #cf_span[k]（#cf_span[1 ≤ t, k ≤ 1000]）——区间数量和数字间的距离。接下来的 #cf_span[t] 行每行包含一对整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[1 ≤ l ≤ r ≤ 101000]）。所有数字均无前导零。每行中的数字由恰好一个空格分隔。\n\n输出 #cf_span[t] 行。每行输出一个整数——对应区间的答案，对 #cf_span[1000000007]（#cf_span[109 + 7]）取模。"},{"iden":"input","content":"第一行包含两个整数 #cf_span[t] 和 #cf_span[k]（#cf_span[1 ≤ t, k ≤ 1000]）——区间数量和数字间的距离。接下来的 #cf_span[t] 行每行包含一对整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[1 ≤ l ≤ r ≤ 101000]）。所有数字均无前导零。每行中的数字由恰好一个空格分隔。"},{"iden":"output","content":"输出 #cf_span[t] 行。每行输出一个整数——对应区间的答案，对 #cf_span[1000000007]（#cf_span[109 + 7]）取模。"},{"iden":"examples","content":"输入1 21 100输出4输入1 270 77输出2输入2 11 2080 100输出00"},{"iden":"note","content":"在第一个样例中，四个近幸运数是 44、47、74、77。在第二个样例中，只有 74 和 77 在给定区间内。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ \\mathcal{L} = \\{4, 7\\} $ be the set of lucky digits.  \nA number is *nearly lucky* with parameter $ k $ if it contains at least two lucky digits at positions $ i, j $ (in decimal representation, 1-indexed from left) such that $ |i - j| \\leq k $.  \n\nLet $ t \\in \\mathbb{Z}^+ $ be the number of test cases.  \nLet $ k \\in \\mathbb{Z}^+ $ be the maximum allowed distance between lucky digits.  \nFor each test case $ i \\in \\{1, \\dots, t\\} $, let $ [l_i, r_i] $ be a range of positive integers (given as decimal strings without leading zeros), with $ 1 \\leq l_i \\leq r_i \\leq 10^{1000} $.  \n\n**Constraints**  \n1. $ 1 \\leq t \\leq 1000 $  \n2. $ 1 \\leq k \\leq 1000 $  \n3. $ l_i, r_i $ are decimal strings of length up to 1001.  \n\n**Objective**  \nFor each segment $ [l_i, r_i] $, compute:  \n$$\n\\text{ans}_i = \\left| \\left\\{ n \\in [l_i, r_i] \\,\\middle|\\, n \\text{ is nearly lucky with parameter } k \\right\\} \\right| \\mod 1000000007\n$$","simple_statement":null,"has_page_source":false}