Тачибана Канаде очень любит Мапо Тофу. Однажды в столовой приготовили очень много самых разных тофу, но не всякое тофу — Мапо Тофу. Мапо Тофу — это достаточно острое тофу.
Каждый кусочек тофу в столовой имеет свой идентификатор — число, записанное в системе счисления с основанием m. Диапазон идентификаторов — это интервал [l, r] (l и r — числа в системе счисления с основанием m), и для каждого числа из этого диапазона существует кусочек тофу с таким идентификатором.
Чтобы определить, какое тофу Мапо Тофу, Тачибана Канаде выбрала n строк из цифр в системе счисления с основанием m и для каждой строки определила некоторое значение. Теперь Тачибана Канаде хочет посчитать для каждого кусочка тофу его значение следующим образом. Изначально значение кусочка тофу равно 0. Если какая-то из n выбранных строк встречается в идентификаторе тофу как подстрока, то значение этой строки нужно добавить к значению этого тофу. Если строка встречается в идентификаторе несколько раз, то и значение прибавляется несколько раз.
Тачибана Канаде считает, что тофу со значением не более k — это Мапо Тофу. И теперь девушка хочет знать, сколько кусочков тофу в столовой являются Мапо Тофу?
Выходные данные
Выведите количество кусочков Мапо Тофу по модулю 1000000007 (109 + 7). Ответ должен быть десятичным целым числом.
Примечание
В первом примере 10, 11 и 100 — единственные три кусочка тофу в отрезке [1, 100] со значением больше 1. Обратите внимание, что значение кусочка тофу 1 равно 1, а не 2, так как идентификаторы не могут содержать ведущих нулей и следовательно, не могут записываться как «01».
Во втором примере ни у одного кусочка на данном интервале нет значения больше 12.
В третьем примере 110000 и 110001 — единственные два идентификатора на данном интервале со значением не больше 6.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 10 1
1 1
3 1 0 0
1 1 1
1 0 1
|
97
|
|
2
|
2 10 12
2 5 9
6 6 3 5 4 9 7
2 0 6 1
3 6 7 2 1
|
635439
|
|
3
|
4 2 6
6 1 0 1 1 1 0
6 1 1 0 1 0 0
1 1 2
3 0 1 0 5
4 0 1 1 0 4
3 1 0 1 2
|
2
|