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: MEDIUM_HARD
Tags: Combinatorics

Mathematics

Starter code:

Solutions:
from sys import stdin
s = input()
(k,) = map(int, stdin.readline().split())
n = len(s)
MOD = 10 ** 9 + 7
numbers = 0
for i in range(n):
	if s[i] == '0' or s[i] == '5':
		numbers += pow(2, i, MOD)
a = 1 - pow(2, n * k, MOD) % MOD
b = 1 - pow(2, n, MOD)
inverse_b = pow(b, MOD - 2, MOD)
sumx = a * inverse_b % MOD
resp = sumx * numbers % MOD
print(int(resp))


(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)


ar = list(map(int, input()))
ar1 = []
ar2 = []
k = 0
MOD = 10 ** 9 + 7
bebe = 1
for i in range(len(ar)):
	if ar[i] % 5 == 0:
		k += bebe
		k %= MOD
	bebe *= 2
	bebe %= MOD
day = int(input())
num1 = pow(2, len(ar) * day, MOD) - 1
if num1 == -1:
	num1 = MOD - 1
num2 = pow(2, len(ar), MOD) - 1
if num2 == -1:
	num2 = MOD - 1
print(num1 * k % MOD * pow(num2, MOD - 2, MOD) % MOD)


mod = 1000000007

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)


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)


(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)


import sys
from math import gcd, sqrt
from collections import defaultdict, Counter, deque
import math
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def get_sum(bit, i):
	s = 0
	i += 1
	while i > 0:
		s += bit[i]
		i -= i & -i
	return s

def update(bit, n, i, v):
	i += 1
	while i <= n:
		bit[i] += v
		i += i & -i

def modInverse(b, m):
	g = math.gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)
s = input()
n = len(s)
k = int(input())
ha = []
ans = 0
mod = 10 ** 9 + 7
for i in range(n):
	if s[i] == '0' or s[i] == '5':
		ha.append(i)
ans = 0
for i in ha:
	z1 = pow(pow(2, n, mod), k, mod) - 1
	z1 %= mod
	z2 = modInverse(pow(2, n, mod) - 1, mod)
	z3 = z1 * z2
	z3 %= mod
	z4 = pow(2, i, mod)
	ans += z3 * z4
	ans %= mod
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)


def run():
	ss = str(input())
	k = int(input())
	m = 1000000007
	summ = 0
	indexes = []
	for index in range(len(ss), 0, -1):
		if ss[index - 1] in '05':
			indexes.append(index)
	for index in indexes:
		summ += pow(2, index - 1, m) % m
	x = pow(2, len(ss) * k, m) - 1 + m
	y = pow(2, len(ss), m) - 1 + m
	f = x * pow(y, m - 2, m) % m
	print(summ * f % m)
	return
run()


(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)


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
print(Ans)


s = input()
n = len(s)
k = int(input())
arr = []
for i in range(n):
	if s[i] == '5' or s[i] == '0':
		arr.append(i)
mod = 10 ** 9 + 7
ss = 0
for i in arr:
	ss += pow(2, i, mod)
pp = pow(2, n * k, mod)
pp = (pp - 1 + mod) % mod
tt = pow(2, n, mod)
tt = (tt - 1 + mod) % mod
pp = pp * pow(tt, mod - 2, mod) % mod
print(pp * ss % mod)


MOD = int(1000000000.0 + 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)


MOD = int(1000000000.0 + 7)

def fast_power(x, y):
	res = 1
	while y > 0:
		if y % 2 == 1:
			res = res * x % MOD
		x = x * x % MOD
		y //= 2
	return res
s = input()
n = len(s)
k = int(input())
a = fast_power(2, n * k) - 1
b = fast_power(2, n) - 1
c = fast_power(b, MOD - 2)
p = a * c % MOD
res = 0
for i in range(n):
	if s[i] == '0' or s[i] == '5':
		res = (res + p) % MOD
	p = p * 2 % MOD
print(res)


import math
s = input()
k = int(input())
md = 10 ** 9 + 7

def modInverse(b, m):
	g = math.gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def modDivide(a, b, m):
	a = a % m
	inv = modInverse(b, m)
	return inv * a % m

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
a = []
for i in range(len(s)):
	if s[i] == '5' or s[i] == '0':
		a += [i]
k2 = pow(2, len(s) * k, md) - 1
a2 = pow(2, len(s), md) - 1
kk = modDivide(k2, a2, md)
ans = 0
for i in a:
	ans = (ans + pow(2, i, md)) % md
ans = ans * kk % md
print(ans)


from sys import stdin, stdout
nmbr = lambda : int(stdin.readline())
lst = lambda : list(map(int, stdin.readline().split()))

def modexp(base, power, M):
	ans = 1
	while power > 0:
		if power & 1:
			ans = ans * base % M
		power >>= 1
		base = base * base % M
	return ans
M = 10 ** 9 + 7
for _ in range(1):
	s = input()
	n = len(s)
	k = nmbr()
	cr = n
	a = 0
	for i in range(n):
		if s[i] == '0' or s[i] == '5':
			a = (a + modexp(2, i, M)) % M
	cr_n = modexp(2, cr * k, M)
	num = a * (cr_n - 1 + M) % M
	den = (modexp(2, cr, M) - 1 + M) % M
	den = modexp(den, M - 2, M) % M
	print(num * den % M)


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)


import sys
input = sys.stdin.readline
read = lambda : map(int, input().split())

def ceil(x):
	if x != int(x):
		x = int(x) + 1
	return x

def factorial(x, m):
	val = 1
	while x > 0:
		val = val * x % m
		x -= 1
	return val

def fact(x):
	val = 1
	while x > 0:
		val *= x
		x -= 1
	return val

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // math.gcd(a, b)

def nCr(n, k):
	if k > n:
		return 0
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return int(res)

def primefs(n):
	primes = {}
	while n % 2 == 0 and n > 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0 and n > 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	p = x
	while p != link[p]:
		p = link[p]
	while x != p:
		nex = link[x]
		link[x] = p
		x = nex
	return p

def union(x, y, link, size):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

def sieve(n):
	prime = [True for i in range(n + 1)]
	(prime[0], prime[1]) = (False, False)
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def phi(n):
	result = n
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n = n // p
			result = result * (1.0 - 1.0 / float(p))
		p = p + 1
	if n > 1:
		result = result * (1.0 - 1.0 / float(n))
	return int(result)

def is_prime(n):
	if n == 0:
		return False
	if n == 1:
		return True
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True
MAXN = int(100000.0 + 5)

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
spf = [0 for i in range(MAXN)]

def factoriazation(x):
	res = []
	for i in range(2, int(x ** 0.5) + 1):
		while x % i == 0:
			res.append(i)
			x //= i
	if x != 1:
		res.append(x)
	return res

def factors(n):
	res = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			res.append(i)
			res.append(n // i)
	return list(set(res))

def int_array():
	return list(map(int, input().strip().split()))

def float_array():
	return list(map(float, input().strip().split()))

def str_array():
	return input().strip().split()

def binary_search(low, high, w, h, n):
	while low < high:
		mid = low + (high - low) // 2
		if check(mid, w, h, n):
			high = mid
		else:
			low = mid + 1
	return low

def check(time, m, assistants):
	summ = 0
	for p in assistants:
		time_needed_with_rest = p[0] * p[1] + p[2]
		time_needed_without_rest = p[0]
		baloons_can_be_inflated = p[1]
		summ += time // time_needed_with_rest * baloons_can_be_inflated
		ntime = time % time_needed_with_rest
		summ += min(ntime // time_needed_without_rest, baloons_can_be_inflated)
	return summ >= m
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
from itertools import permutations
import math
import bisect as bis
import random
import sys

def solve():
	a = input().rstrip()
	k = int(input())
	s = 0
	x = pow(2, len(a) * k, MOD) - 1 + MOD
	y = pow(2, len(a), MOD) - 1 + MOD
	f = x * pow(y, MOD - 2, MOD) % MOD
	for i in range(len(a)):
		if a[i] == '5' or a[i] == '0':
			s = (s + pow(2, i, MOD)) % MOD
	print(s * f % MOD)
for _ in range(1):
	solve()


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)


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)


mod = 10 ** 9 + 7

def fastmod(x, y):
	res = 1
	while y > 0:
		if y & 1:
			res = res * x % mod
		x = x * x % mod
		y //= 2
	return res
s = input()
n = len(s)
k = int(input())
p = (fastmod(2, n * k) - 1) * fastmod(fastmod(2, n) - 1, mod - 2) % mod
ans = 0
for i in range(n):
	if s[i] == '0' or s[i] == '5':
		ans = (ans + p) % mod
	p = p * 2 % mod
print(ans)


MOD = 1000000007
n = input()
sz = len(n)
a = int(input())
ans = 0
for i in range(sz):
	if n[i] == '0' or n[i] == '5':
		ans += pow(2, i, MOD)
		ans %= MOD
print(ans * (pow(2, a * sz, MOD) - 1) * pow(pow(2, sz, MOD) - 1, MOD - 2, 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):
	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 + 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)


from sys import stdin
input = lambda : stdin.readline().strip()
lin = lambda : list(map(int, input().split()))
iin = lambda : int(input())
main = lambda : map(int, input().split())
from math import ceil, sqrt, factorial, log
from collections import deque
from bisect import bisect_left

def gcd(a, b):
	(a, b) = (max(a, b), min(a, b))
	while a % b != 0:
		(a, b) = (b, a % b)
	return b
mod = 998244353
mod = 1000000007

def inverse(a):
	return pow(a, mod - 2, mod)

def solve(we):
	s = input()
	k = iin()
	n = len(s)
	t = 0
	ans = (pow(2, n * k, mod) - 1 + mod) % mod * (inverse(pow(2, n) - 1 + mod) % mod) % mod
	for i in range(len(s)):
		if s[i] in ['0', '5']:
			t = (t % mod + pow(2, i, mod)) % mod
	ans = ans * t % mod
	print(ans)
qwe = 1
for _ in range(qwe):
	solve(_ + 1)


n = input()
k = int(input())
X = list(n)
index = []
mo = 1000000007
for i in range(len(X)):
	if X[i] == '0' or X[i] == '5':
		index.append(i)
ans = 0
R = pow(2, len(X), mo)
for i in index:
	ans = (ans + pow(2, i, mo)) % mo
ans = ans * (pow(R, k, mo) - 1) * pow(R - 1, mo - 2, mo) % mo
print(ans)


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

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m

def b2i(s):
	ans = 0
	for i in range(len(s)):
		ans += s[i] * pow(2, i, mod)
		ans %= mod
	return ans
from sys import stdin
inp = stdin.readline
mod = 1000000007
(s, k) = (inp(), int(inp()))
m = len(s) - 1
x = b2i([0 if int(i) % 5 else 1 for i in s if i.isdigit()])
print(x * (pow(2, m * k, mod) - 1) * modinv(pow(2, m, mod) - 1, mod) % mod)


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)


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)