Horse Races

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만 주어진 구간에 포함된다.