CF327C.Magic Five

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 (109 + 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.

有一块长为 $s$ 的数字板，上面包含 $n$ 个数字。Iahub 想要删除其中一些数字（可以不删，但不允许删掉所有数字），从而在板上形成他的“魔法数字”——一个能被 $5$ 整除的数。注意：所得数字可能包含前导零。

现在 Iahub 想要计算得到魔法数字的方法总数，结果对 $1000000007$（即 $10^9 + 7$）取模。若两次操作所删除的位置集合不同，则视为两种不同的方法。

请参见题面输入部分，$s$ 以一种特殊形式给出。

In the first line you're given a string a (1 ≤ |a| ≤ 105), containing digits only. In the second line you're given an integer k (1 ≤ k ≤ 109). The plate s is formed by concatenating k copies of a together. That is n = |a|·k.

第一行给出一个仅包含数字的字符串 $a$（$1 \le |a| \le 10^5$）。第二行给出一个整数 $k$（$1 \le k \le 10^9$）。车牌号字符串 $s$ 由将 $a$ 重复拼接 $k$ 次构成，即 $n = |a|·k$。

Print a single integer — the required number of ways modulo 1000000007 (109 + 7).

输出一个整数——满足要求的方案数对 1000000007（即 $10^9 + 7$）取模的结果。

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 26 - 1 = 63 possible ways to delete digits.

第一种情况中，有四种可能的方式构造一个能被 5 整除的数：5、15、25 和 125。

第二种情况中，请记住要将 a 的副本进行拼接。实际的号码牌是 1399013990。

第三种情况中，除了删除所有数字外，其余任意选择均可。因此共有 $2^6 - 1 = 63$ 种可能的删数字方式。