Radical loves magic things.Today,he wants to do some amazings about numbers.
He has a number N , he wants to delete some digits (possibly none, but he is not allowed to delete all the digits)
to form his "magic number" , a number that is divisible by 5. Note that, the resulting number may contain leading zeros.
Now he wants to count the number of ways he can obtain magic number, modulo 1000000007 (1e9+7).
Two ways are different, if the set of deleted positions in N differs.
Look at the input part of the statement, N is given in a special form.

In the first line you're given a string a (1≤|a|≤1e5), containing digits only. In the second line you're given an integer k (1≤ k≤1e9).
The number N is formed by concatenating k copies of a together. That is N=|a|·k.

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