← 返回题目列表

Codeforces · 327/C

C. 魔法五

中文机器翻译题面 查看原题

有一个长板 s,包含 n 个数字。 Iahub 想要删除一些数字(可能没有,但不允许删除所有数字)以在车牌上形成他的“魔数”,一个能被 5 整除的数字。请注意,结果数字可能包含前导零。

现在 Iahub 想要计算他可以获得幻数的方式数量,模 1000000007 (109 + 7)。如果 s 中删除位置的集合不同,则两种方法是不同的。

看语句的输入部分,s是以特殊形式给出的。

输入

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

输出

打印单个整数 — 所需的路数以 1000000007 (109 + 7) 为模。

示例

输入 #1

1256
1

输出 #1

4

输入 #2

13990
2

输出 #2

528

输入 #3

555
2

输出 #3

63

注意

在第一种情况下,有四种可能的方法来生成可被 5 整除的数字:5、15、25 和 125。

在第二种情况下,请记住连接 a 的副本。实际车牌是1399013990。

第三种情况,除了删除所有数字外,任何选择都可以。因此,有 26 - 1 = 63 种可能的删除数字的方法。