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 (10^9 + 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| ≤ 10^5), containing digits only. In the second line you're given an integer k (1 ≤ k ≤ 10^9). 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 (10^9 + 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 2^6 - 1 = 63 possible ways to delete digits.

Difficulty: interview

Starter code:

Solutions:
a = input()
k = int(input())
n = len(a)
ans = 0
MOD = 10 ** 9 + 7
m = 1 - pow(2, n * k, MOD)
m *= pow(1 - pow(2, n, MOD), MOD - 2, MOD)
m %= MOD
for i in range(n - 1, -1, -1):
    if a[i] == '0' or a[i] == '5':  
        ans += (m * pow(2, i, MOD)) % MOD
ans = ans % MOD
if ans < 0:
    ans += MOD
print(ans)
    


mod = 1000000007

def egcd(a, b):
    d = a
    if b != 0:
        d, y, x = egcd(b, a%b)
        y -= (a // b) * x
        return d, x, y
    else:
        return a, 1, 0

def inv(a, m):
    d, x, y = egcd(a, m)
    return (m+x%m)%m


a = input()
k = int(input())
t = len(a)
d = 0
for i, c in enumerate(a):
    if not int(c) % 5:
        d += pow(2, i, mod)
        d %= mod
d %= mod
print(d*(pow(2, k*t, mod)-1)*inv((pow(2, t, mod)-1)%mod, mod)%mod)



s=input()
k=int(input())
N=len(s)
m=1000000007

a=m+1-pow(2,N*k,m)
b=m+1-pow(2,N,m)
l=(a*pow(b,m-2,m))%m

p=0
for i in range(N):
    if s[i] in ('0','5'):
        p=(p+pow(2,i,m))

print((p*l)%m)


mod = 1000000007

#gcd(a, m) = 1
def inv_mod(a, m):
    a %= m
    return pow(a, m-2, m)


a = input()
k = int(input())
t = len(a)
d = 0
for i, c in enumerate(a):
    if not int(c) % 5:
        d += pow(2, i, mod)
        d %= mod
print(d*(pow(2, k*t, mod)-1)*inv_mod(pow(2, t, mod)-1, mod)%mod)


mod = 1000000007

#gcd(a, m) = 1
def inv_mod(a, m):
    a %= m
    return pow(a, m-2, m)


a = input()
k = int(input())
t = len(a)
d = 0
for i, c in enumerate(a):
    if not int(c) % 5:
        d += pow(2, i, mod)
        d %= mod
print(d*(pow(2, (k*t)%(mod-1), mod)-1)*inv_mod(pow(2, t, mod)-1, mod)%mod)


mod = 1000000007

#gcd(a, m) = 1
def inv_mod(a, m):
    a %= m
    return pow(a, m-2, m)


a = input()
k = int(input())
t = len(a)
d = 0
i = 1
for c in a:
    if not int(c) % 5:
        d += i
        d %= mod
    i *= 2
    i %= mod
print(d*(pow(2, (k*t)%(mod-1), mod)-1)*inv_mod(pow(2, t, mod)-1, mod)%mod)


mod = 1000000007

#gcd(a, m) = 1
def inv_mod(a, m):
    a %= m
    return pow(a, m-2, m)


a = input()
k = int(input())
t = len(a)
d = 0
i = 1
for c in a:
    if not int(c) % 5:
        d = (d+i)%mod
    i = (i*2)%mod
print(d*(pow(2, (k*t)%(mod-1), mod)-1)*inv_mod(pow(2, t, mod)-1, mod)%mod)


mod = 1000000007

#gcd(a, m) = 1
def inv_mod(a, m):
    a %= m
    return pow(a, m-2, m)


a = input()
k = int(input())
t = len(a)
d = 0
i = 1
for c in a:
    if c in ('0', '5'):
        d = (d+i)%mod
    i = (i*2)%mod
print(d*(pow(2, (k*t)%(mod-1), mod)-1)*inv_mod(pow(2, t, mod)-1, mod)%mod)


mod = 1000000007

#gcd(a, m) = 1
def inv_mod(a, m):
    a %= m
    return pow(a, m-2, m)


a = input()
k = int(input())
t = len(a)
d = 0
i = 1
for c in a:
    if c in ('0', '5'):
        d = (d+i)%mod
    i = (i*2)%mod
print(d*(pow(2, k*t, mod)-1)*inv_mod(pow(2, t, mod)-1, mod)%mod)


mod = 1000000007

#gcd(a, m) = 1
def inv_mod(a, m):
    a %= m
    return pow(a, m-2, m)


a, k = input(), int(input())
t, d, i = len(a), 0, 1

for c in a:
    if c in ('0', '5'):
        d = (d+i)%mod
    i = (i*2)%mod
print(d*(pow(2, k*t, mod)-1)*inv_mod(pow(2, t, mod)-1, mod)%mod)


input_string = input()
n = int(input())
len_tmp = len(input_string)
const = 1000000007

def fast_pow(a, b, mod):
    c=bin(b)[2:]
    result=1
    for i in c:
        result = (result*result * a**int(i))%mod
    return result

def inverse(a, mod):
    #mod-простое
    return fast_pow(a, mod-2, mod)
#-------------------------------
num = 0
tmp = 1
"""
for i in range(len_tmp):
    if int(input_string[i])%5==0:
        num = (num + fast_pow(2, i, const))
"""
for i in range(len_tmp):
    if int(input_string[i])%5==0:
        num = (num + tmp)
    tmp=(tmp*2)%const
num %= const
l = fast_pow(2, len_tmp, const)
print((num*(fast_pow(l, n, const)-1)*inverse(l-1, const))%const)

MOD = 1000000007
data = input().strip()
k = int(input())
ans = 0
alc = 1
for i, d in enumerate(data):
    if d == "0" or d == "5":
        ans += alc
    alc *= 2
    alc %= MOD
print(ans * (pow(alc, k, MOD) - 1) * pow(alc - 1, MOD - 2, MOD) % MOD)



import sys
fin = sys.stdin
M = 1000000007

def egcd(a, b):
    d = a
    if b != 0:
        d, y, x = egcd(b, a % b)
        y -= (a // b) * x
        return d, x, y
    else:
        return a, 1, 0

def inv(a, m):
    d, x, y = egcd(a, m)
    return (m + x % m) % m

a = fin.readline().strip()
k = int(fin.readline())
n = len(a)
D = (inv(pow(2, n, M) - 1, M) * (pow(2, n * k, M) - 1)) % M
S = 0
for i in range(n):
    if a[i] in ['0', '5']:
        S = (S + pow(2, i, M)) % M
print((D * S) % M)

s=input()
k=int(input())

p=10**9+7
n=len(s)
amodp = (pow(2,k*n,p)-1)%p

b1modp = pow ( (2**n) -1 , p-2 , p )

MOD = (amodp*b1modp) % p
ans=0
for i in range(len(s)):
    if(s[i]=='5' or s[i]=='0'):
        ans+=pow(2,i,10**9+7)
Ans=0

Ans+= ans*( MOD )

Ans%=p
##for i in range(k):
##    Ans+=ans*pow(2,i*len(s),10**9+7)

print(Ans)
    

##x^k - 1
##---------
##x  - 1
##
##
##x = 2**n
##
##2^kn - 1
##---------
##2^n - 1
##
##amodp = (pow(2,k*n,p)-1)%p
##
##b1modp = pow ( 2**k-1 , p-2 , p )
##
##MOD = (amodp*b1modp) % p
##
##
##
##(a / b) mod p = ((a mod p) * (b^(-1) mod p)) mod p
##
##b^(-1) mod p = b^(p - 2) mod p


t, k = input(), int(input())
n, d = len(t), 1000000007
p = (pow(2, k * n, d) - 1) * pow(pow(2, n, d) - 1, d - 2, d) % d
print(p * sum(pow(2, i, d) for i in range(n) if t[i] in '05') % d)

t, k = input(), int(input())
t = t.replace('5', '0')
n, d = len(t), 1000000007
s, j = 0, 1
for i in range(n):
    if t[i] == '0': s += j
    j = (2 * j) % d
print(((pow(j, k, d) - 1) * pow(j - 1, d - 2, d) % d) * (s % d) % d)

t, k = input(), int(input())
s, n, d = 0, 1, 1000000007
for i in t:
    if i in '05': s += n
    n = (n << 1) % d
p = (pow(n, k, d) - 1) * pow(n - 1, d - 2, d)
print((p % d) * (s % d) % d)

s=input()
k=int(input())

p=10**9+7
n=len(s)
amodp = (pow(2,k*n,p)-1)%p

b1modp = pow ( (pow(2,n,p) -1 + p)%p , p-2 , p )

MOD = (amodp*b1modp) % p
ans=0
for i in range(len(s)):
    if(s[i]=='5' or s[i]=='0'):
        ans+=pow(2,i,10**9+7)
Ans=0

Ans+= ans*( MOD )

Ans%=p
##for i in range(k):
##    Ans+=ans*pow(2,i*len(s),10**9+7)

print(Ans)

s=input()
k=int(input())

p=10**9+7
n=len(s)
amodp = (pow(2,k*n,p)-1)%p

b1modp = pow ( (2**n) -1 , p-2 , p )

MOD = (amodp*b1modp) % p
ans=0
for i in range(len(s)):
    if(s[i]=='5' or s[i]=='0'):
        ans+=pow(2,i,10**9+7)
Ans=0

Ans+= ans*( MOD )

Ans%=p
##for i in range(k):
##    Ans+=ans*pow(2,i*len(s),10**9+7)

print(Ans)
    

##x^k - 1
##---------
##x  - 1
##
##
##x = 2**n
##
##2^kn - 1
##---------
##2^n - 1
##
##amodp = (pow(2,k*n,p)-1)%p
##
##b1modp = pow ( 2**k-1 , p-2 , p )
##
##MOD = (amodp*b1modp) % p
##
##
##
##(a / b) mod p = ((a mod p) * (b^(-1) mod p)) mod p
##
##b^(-1) mod p = b^(p - 2) mod p


def invmod( x , y , MOD ):
    return (x*pow(y,MOD-2,MOD))%MOD

s=input()
k=int(input())
n=len(s)
MOD=10**9+7
sumG = invmod( pow(2,k*n,MOD)-1 , pow(2,n,MOD)-1 , MOD)
ans=0
for i in range(len(s)):
    if(s[i]=='5' or s[i]=='0'):
        ans+=pow(2,i,MOD)
ans*=sumG
print(ans%MOD)



A = input()
n = int(input())
m = 1000000007
a = len(A)

x = pow(2,a*n,m)-1+m
y = pow(2,a,m)-1+m
f = x*pow(y,m-2,m)%m

s = 0
for r in range(a):
	if A[r] in '05':
		s = (s+pow(2,r,m))%m
print((s*f)%m)


#   C:\Users\Usuario\HOME2\Programacion\ACM


MOD = int( 1e9 + 7 )

A = input()
K = int( input() )

ans = 0
q = 1
for i in range( len( A ) ):
  if A[ i ] == '0' or A[ i ] == '5':
    ans = ( ans + q ) % MOD
  q = q * 2 % MOD

print( ans * ( pow( 2, K * len( A ), MOD ) - 1 ) * pow( pow( 2, len( A ), MOD ) - 1, MOD - 2, MOD ) % MOD )


A = input()
n = int(input())
m = 1000000007
a = len(A)

x = pow(2,a*n,m)-1+m
y = pow(2,a,m)-1+m
f = x*pow(y,m-2,m)%m

s = 0
for r in range(a):
	if A[r] in '05':
		s = (s+pow(2,r,m))%m
print((s*f)%m)

a,k = input(), int(input())
n,m = len(a), 10 ** 9 + 7

ans = 0
t = (pow(2, k * n, m) - 1) * pow(pow(2, n, m) - 1, m - 2, m) % m
for i in range(n - 1, -1, -1):
  if int(a[i]) % 5 == 0:
    ans = (ans + pow(2, i, m) * t) % m

print(ans)


a,k = input(), int(input())
n,m = len(a), 10 ** 9 + 7

ans = 0
t = (pow(2, k * n, m) - 1) * pow(pow(2, n, m) - 1, m - 2, m) % m
for i in range(n - 1, -1, -1):
  if int(a[i]) % 5 == 0:
    ans = (ans + pow(2, i, m) * t) % m

print(ans)

# comentario