Петя очень любит конные скачки. В скачках принимают участие лошади с номерами от l до r включительно. Петя хочет оценить вероятность выигрыша, для этого ему зачем-то нужно найти количество почти счастливых номеров лошадей. Номер называется почти счастливым, если в нем есть хотя бы две счастливые цифры, расстояние между которыми не превосходит k. От львовских ребят Петя узнал, что счастливые цифры — это цифры 4 и 7. Расстояние между цифрами — это модуль разности между их позициями в числе. Например, при k = 2 номера 412395497, 404, 4070400000070004007 являются почти счастливыми, а номера 4, 4123954997, 4007000040070004007 — не являются.
Петя подготовил t отрезков [li, ri] и придумал общее для всех отрезков число k. Ваша задача — найти для каждого отрезка количество почти счастливых чисел в нем по модулю 1000000007 (109 + 7).
Выходные данные
Выведите t строк. В каждой из их выведите одно число — ответ для соответствующего теста по модулю 1000000007 (109 + 7).
Примечание
В первом примере имеется четыре почти счастливых числа: 44, 47, 74, 77.
Во втором примере только 74 и 77 попадают в данный отрезок.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 2
1 100
|
4
|
|
2
|
1 2
70 77
|
2
|
|
3
|
2 1
1 20
80 100
|
0
0
|