경마

Petya는 경마를 매우 좋아한다. l부터 r까지의 번호가 매겨진 말들이 경주에 참가한다. Petya는 우승 확률을 계산하고 싶어 하며, 어떤 이유에서인지 그러기 위해서는 거의 행운인 말 번호의 개수를 알아야 한다. 거의 행운인 수란 거리가 k을 넘지 않는 행운의 숫자가 적어도 두 개 있는 정수이다. Petya는 Lviv 출신 친구 몇 명에게서 행운의 숫자는 숫자 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)로 나눈 나머지를 나타내는 정수 하나를 출력한다.

첫 번째 예제에서 거의 행운인 수 네 개는 44, 47, 74, 77이다.

두 번째 예제에서는 74와 77만 주어진 구간에 포함된다.