Magic Five

题意翻译

给定一个有 $n$ 个数字的字符串 $s$ ( $s$ 是循环了 $k$ 次的字符串 $a$ )。 $Iahub$ 想要删除一些其中的数字(有可能不删，但是不能删完所有的数字)让这个数成为能被五整除的“魔法数字”。注意：给出的数字可能含有前导0。 现在Iahub想要数出他能得到他的“魔法数字”的方法总数，答案 $mod$ 1000000007(10^9+7)。如果 $s$ 中数字删除的位置不同，那么我们就认为他们是不同的方法。

题目描述

There is a long plate $ s $ containing $ n $ digits. Iahub wants to delete some digits (possibly none, but he is not allowed to delete all the digits) to form his "magic number" on the plate, a number that is divisible by $ 5 $ . Note that, the resulting number may contain leading zeros. Now Iahub wants to count the number of ways he can obtain magic number, modulo $ 1000000007 $ ( $ 10^{9}+7 $ ). Two ways are different, if the set of deleted positions in $ s $ differs. Look at the input part of the statement, $ s $ is given in a special form.

输入输出格式

输入格式

In the first line you're given a string $ a $ ( $ 1<=|a|<=10^{5} $ ), containing digits only. In the second line you're given an integer $ k $ ( $ 1<=k<=10^{9} $ ). The plate $ s $ is formed by concatenating $ k $ copies of $ a $ together. That is $ n=|a|·k $ .

输出格式

Print a single integer — the required number of ways modulo $ 1000000007 $ ( $ 10^{9}+7 $ ).

输入输出样例

输入样例 #1

1256
1

输出样例 #1

4

输入样例 #2

13990
2

输出样例 #2

528

输入样例 #3

555
2

输出样例 #3

63

说明

In the first case, there are four possible ways to make a number that is divisible by 5: 5, 15, 25 and 125. In the second case, remember to concatenate the copies of $ a $ . The actual plate is 1399013990. In the third case, except deleting all digits, any choice will do. Therefore there are $ 2^{6}-1=63 $ possible ways to delete digits.