CF327C Magic Five

有一个长条形牌子 $s$，上面包含 $n$ 个数字。Iahub 想要删除其中一些数字（可以一个都不删，但不允许全部删除），使得牌子上剩下的数字组成他的“魔法数字”。所谓魔法数字，就是能被 $5$ 整除的数字。注意，最终得到的数字可以有前导零。 现在，Iahub 想要统计有多少种不同的删除位置集合可以得到魔法数字，答案对 $1000000007$（$10^{9}+7$）取模。两种方法不同，当且仅当它们在 $s$ 中被删除的数字的位置集合不同。 请注意，输入中的 $s$ 是以特殊的方式给出的。

第一行一个仅包含数字的字符串 $a$，$1 \leq |a| \leq 10^{5}$。 第二行一个整数 $k$，$1 \leq k \leq 10^{9}$。 牌子 $s$ 是由 $k$ 个 $a$ 串联得到的，也即 $n = |a| \cdot k$。

输出一个整数，表示可以得到魔法数字的方法数，模 $1000000007$。

第一组数据，魔法数字共有四种可能分别为：5、15、25 和 125。 第二组数据，需要将 $a$ 拼接 $k$ 次，真实的牌子是 1399013990。 第三组数据，除了全部删除数字外，任何选择都可行。因此，共有 $2^{6}-1=63$ 种删除方法。 由 ChatGPT 5 翻译