E. Horse Races

Codeforces

IDCF96E

Time2000ms

Memory256MB

Difficulty—

English · Original

Chinese · Translation

Formal · Original

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). ## Input 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. ## Output Output _t_ lines. In each line print one integer — the answer for the corresponding segment modulo 1000000007 (109 + 7). [samples] ## Note 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.

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] 则不是。 Petya 准备了 #cf_span[t] 个区间 #cf_span[[li, ri]]，并为所有区间发明了一个共同的数字 #cf_span[k]。你的任务是找出每个区间中有多少个近幸运数。由于答案可能很大，请对 #cf_span[1000000007]（#cf_span[109 + 7]）取模输出。第一行包含两个整数 #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]）。所有数字均不带前导零。每行中的数字由恰好一个空格分隔。输出 #cf_span[t] 行。每行输出一个整数——对应区间答案对 #cf_span[1000000007]（#cf_span[109 + 7]）取模的结果。在第一个样例中，四个近幸运数是 44、47、74、77。在第二个样例中，只有 74 和 77 在给定区间内。 ## Input 第一行包含两个整数 #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]）。所有数字均不带前导零。每行中的数字由恰好一个空格分隔。 ## Output 输出 #cf_span[t] 行。每行输出一个整数——对应区间答案对 #cf_span[1000000007]（#cf_span[109 + 7]）取模的结果。 [samples] ## Note 在第一个样例中，四个近幸运数是 44、47、74、77。在第二个样例中，只有 74 和 77 在给定区间内。

**Definitions** Let $ \mathcal{D} = \{4, 7\} $ be the set of lucky digits. A number is *nearly lucky* with parameter $ k $ if it contains at least two lucky digits at positions $ i, j $ (1-indexed from left) such that $ |i - j| \leq k $. Let $ t, k \in \mathbb{Z}^+ $ with $ 1 \leq t, k \leq 1000 $. Let each test case be defined by an interval $ [l_i, r_i] $, where $ l_i, r_i \in \mathbb{Z} $, $ 1 \leq l_i \leq r_i \leq 10^{1000} $, given as decimal strings without leading zeros. **Constraints** 1. $ 1 \leq t \leq 1000 $ 2. $ 1 \leq k \leq 1000 $ 3. $ 1 \leq l_i \leq r_i \leq 10^{1000} $ for all $ i \in \{1, \dots, t\} $ **Objective** For each interval $ [l_i, r_i] $, compute: $$ F(l_i, r_i) = \left| \left\{ n \in \mathbb{Z} \mid l_i \leq n \leq r_i \text{ and } n \text{ is nearly lucky with parameter } k \right\} \right| \mod 1000000007 $$

Samples

Input #1

1 2
1 100

Output #1

Input #2

1 2
70 77

Output #2

Input #3

2 1
1 20
80 100

Output #3

0
0

API Response (JSON)

{
  "problem": {
    "name": "E. Horse Races",
    "description": {
      "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 ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF96E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "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 ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Petya 非常喜欢赛马。编号从 #cf_span[l] 到 #cf_span[r] 的马参加比赛。Petya 希望评估获胜的概率；出于某种原因，为此他需要知道“近幸运”马号的数量。一个 #cf_span(class=[tex-font-style-underline], body=[近幸运]) 数是指至少包含两个幸运数字，且这两个数字之间的距离不超过 #cf_span[k] 的整数。Petya ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ \\mathcal{D} = \\{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 $ (1-indexed...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments