有一个长板 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 种可能的删除数字的方法。