ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

6028: Magic Five

内存限制：256 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：5 通过：3
提交提交记录统计Web Board

题目描述

        有一个包含n个数字的长板s。Iahub想要删除一些数字（可能没有，但他不允许删除所有数字）以在盘子上形成他的“幻数”，一个可以被5整除的数字。请注意，结果数字可能包含前导零。
        现在，Iahub想要计算他可以获得幻数，模1000000007的方法的数量 (109+7).如果 s 中的已删除位置集不同，则两种方式是不同的。
查看语句的输入部分，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 (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.
Input
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.
Output
Print a single integer − the required number of ways modulo 1000000007 (109+7).
Examples
Input 
1256
1
Output 
4
Input 
13990
2
Output 
528
Input 
555
2
Output 
63
Note
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.

输入格式

在第一行中，你得到一个字符串 a (1≤|A|≤105），仅包含数字。在第二行中，你得到一个整数 k (1≤k≤109).板 s 是通过将 a 的 k 个副本连接在一起而形成的。即 n=|a|·k.

输出格式

打印单个整数 − 所需的模数1000000007 (109+7).

Input

1256

1

Output

4

Input

13990

2

Output

528

Input

555

2

Output

63

注意

在第一种情况下，有四种可能的方法可以使数字被 5 整除：5、15、25 和 125。
在第二种情况下，请记住连接 a 的副本。实际的盘子是1399013990的。
在第三种情况下，除了删除所有数字外，任何选择都可以。因此有2+-1=63删除数字的可能方法。

输入样例 复制 

1256

1

输出样例 复制 

4

分类标签