C. Волшебная пятерка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана длинная табличка s с n цифрами, записанными на ней в ряд. Яхуб хочет удалить некоторое количество цифр (возможно, нулевое, но удалять все цифры не разрешается), чтобы получить на табличке «волшебное число», число, которое делится на 5. Обратите внимание, что итоговое число может содержать лидирующие нули.

Теперь Яхуб хочет посчитать количество способов, которыми он может получить волшебное число, по модулю 1000000007 (109 + 7). Два способа различны тогда, когда набор удаленных позиций в s различается.

Обратите внимание на описание входных данных, s задана в особой форме.

Входные данные

В первой строке дана строка a (1 ≤ |a| ≤ 105), содержащая только цифры. Во второй строке дано целое число k (1 ≤ k ≤ 109). Строка с цифрами, записанная на таблице s, получается как конкатенация k копий a. То есть, n = |a|·k.

Выходные данные

Выведите единственное целое число — требуемое количество способов по модулю 1000000007 (109 + 7).

Примеры
Входные данные
1256
1
Выходные данные
4
Входные данные
13990
2
Выходные данные
528
Входные данные
555
2
Выходные данные
63
Примечание

В первом тесте есть четыре возможных способа получить число, делимое на 5: 5, 15, 25 и 125.

Во втором тесте не забудьте выполнить конкатенацию копий a. Нужная табличка — 1399013990.

В третьем тесте можно выбрать любой вариант (кроме удаления всех цифр). Следовательно, есть 26 - 1 = 63 возможных способов удалить цифры.