Дана длинная табличка s с n цифрами, записанными на ней в ряд. Яхуб хочет удалить некоторое количество цифр (возможно, нулевое, но удалять все цифры не разрешается), чтобы получить на табличке «волшебное число», число, которое делится на 5. Обратите внимание, что итоговое число может содержать лидирующие нули.
Теперь Яхуб хочет посчитать количество способов, которыми он может получить волшебное число, по модулю 1000000007 (109 + 7). Два способа различны тогда, когда набор удаленных позиций в s различается.
Обратите внимание на описание входных данных, s задана в особой форме.
Выходные данные
Выведите единственное целое число — требуемое количество способов по модулю 1000000007 (109 + 7).
Примечание
В первом тесте есть четыре возможных способа получить число, делимое на 5: 5, 15, 25 и 125.
Во втором тесте не забудьте выполнить конкатенацию копий a. Нужная табличка — 1399013990.
В третьем тесте можно выбрать любой вариант (кроме удаления всех цифр). Следовательно, есть 26 - 1 = 63 возможных способов удалить цифры.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1256
1
|
4
|
|
2
|
13990
2
|
528
|
|
3
|
555
2
|
63
|