AtCoder Beginner Contest 135 - Digits Parade

Given is a string S. Each character in S is either a digit (0, ..., 9) or ?.
Among the integers obtained by replacing each occurrence of ? with a digit, how many have a remainder of 5 when divided by 13? An integer may begin with 0.
Since the answer can be enormous, print the count modulo 10^9+7.

-----Constraints-----
 - S is a string consisting of digits (0, ..., 9) and ?.
 - 1 \leq |S| \leq 10^5

-----Input-----
Input is given from Standard Input in the following format:
S

-----Output-----
Print the number of integers satisfying the condition, modulo 10^9+7.

-----Sample Input-----
??2??5

-----Sample Output-----
768

For example, 482305, 002865, and 972665 satisfy the condition.

Difficulty: MEDIUM_HARD

Starter code:

Solutions:
MOD = 10 ** 9 + 7
s = input()
old_dp = [0] * 13
new_dp = [0] * 13
old_dp[0] = 1
for c in s:
	for i in range(13):
		if c == '?':
			for d in range(10):
				new_dp[(i * 10 + d) % 13] += old_dp[i]
		else:
			new_dp[(i * 10 + int(c)) % 13] += old_dp[i]
	old_dp = [x % MOD for x in new_dp]
	new_dp = [0] * 13
print(old_dp[5])


s = input()
n = len(s)
mod = 10 ** 9 + 7
dp = [[0] * 13 for _ in range(n + 1)]
dp[0][0] = 1
for (i, d) in enumerate(s):
	if d == '?':
		for x in range(10):
			for y in range(13):
				dp[i + 1][(y * 10 + x) % 13] += dp[i][y]
	else:
		d = int(d)
		for y in range(13):
			dp[i + 1][(y * 10 + d) % 13] += dp[i][y]
	for j in range(13):
		dp[i + 1][j] %= mod
print(dp[n][5])


s = input()
mod = 10 ** 9 + 7
n = len(s)
res = [1] + [0] * 12
for ss in s:
	dp = [0] * 13
	for i in range(13):
		dp[10 * i % 13] = res[i]
	dp += dp
	if ss == '?':
		for i in range(13):
			res[i] = sum(dp[i + 4:i + 14])
	else:
		for i in range(13):
			res[i] = dp[i + 13 - int(ss)]
	res = [v % mod for v in res]
print(res[5])


MOD = 10 ** 9 + 7
S = input()
l = len(S)
dp = [[0] * 13 for _ in range(l + 1)]
dp[0][0] = 1
p = 1
for i in range(l):
	if S[i] != '?':
		n = int(S[i])
		for j in range(13):
			dp[i + 1][(j * 10 + n) % 13] += dp[i][j]
	else:
		for k in range(10):
			for j in range(13):
				dp[i + 1][(j * 10 + k) % 13] += dp[i][j]
	for j in range(13):
		dp[i + 1][j] = dp[i + 1][j] % MOD
	p = p * 10 % MOD
print(dp[l][5])


import sys, math, copy

def main():
	input = sys.stdin.readline
	S = ''.join(reversed(input().strip()))
	dp = [0] * 13
	dp_ = [0] * 13
	mod13_tuple = tuple([i % 13 for i in range(12 ** 2 + 1)])
	tuple10 = tuple(range(10))
	tuple13 = tuple(range(13))
	divisor = 10 ** 9 + 7
	dp_[0] = 1
	mul = 1
	for i in range(len(S)):
		s = S[i]
		if s == '?':
			for d in tuple10:
				m = mod13_tuple[d * mul]
				for pm in tuple13:
					dp[mod13_tuple[pm + m]] += dp_[pm]
		else:
			si = int(s)
			m = mod13_tuple[si * mul]
			for pm in tuple13:
				dp[mod13_tuple[pm + m]] = dp_[pm]
		for j in tuple13:
			dp_[j] = dp[j] % divisor
			dp[j] = 0
		mul = mod13_tuple[mul * 10]
	print(dp_[5])
main()


M = 10 ** 9 + 7
a = [1] + [0] * 12
p = 1
for c in input()[::-1]:
	r = range(0, p * 10, p) if c == '?' else (p * int(c),)
	a = [sum((a[(i - j) % 13] for j in r)) % M for i in range(13)]
	p = p * 10 % 13
print(a[5])


def main():
	s = ''.join(reversed(input()))
	multiplier = 1
	divisor = 10 ** 9 + 7
	list10 = list(range(10))
	list13 = list(range(13))
	p = [0] * 13
	np = [0] * 13
	rt = [i % 13 for i in range(121)]
	p[0] = 1
	for i in range(len(s)):
		if s[i] != '?':
			r = rt[int(s[i]) * multiplier]
			for j in list13:
				np[rt[j + r]] = p[j]
		else:
			r = 0
			for j in list10:
				for k in list13:
					np[rt[k + r]] += p[k]
				r = rt[r + multiplier]
		for j in list13:
			p[j] = np[j] % divisor
			np[j] = 0
		multiplier = rt[10 * multiplier]
	print(p[5])
main()


M = 10 ** 9 + 7
r = tuple((tuple(((j - k) * 9 % 13 for j in range(10))) for k in range(13)))
d = [1] + [0] * 12
for c in input():
	if c > '9':
		d = [sum((d[j] for j in k)) % M for k in r]
	else:
		d = [d[(int(c) - k) * 9 % 13] for k in range(13)]
print(d[5])


s = input()
q = s.count('?')
ans = [0] * 13
ans[0] = 1
for v in s:
	dp = [0] * 13
	for j in range(13):
		dp[j * 10 % 13] = ans[j] % 1000000007
	dp += dp
	for j in range(13):
		if v == '?':
			ans[j] = sum(dp[j + 4:j + 14])
		else:
			ans[j] = dp[j - int(v)]
print(ans[5] % 1000000007)


s = input()
n = len(s)
dp = [[0] * 13 for _ in range(100010)]
dp[0][0] = 1
for i in range(n):
	for j in range(10):
		if s[i] == str(j) or s[i] == '?':
			for h in range(13):
				dp[i + 1][(h * 10 + j) % 13] += dp[i][h]
	for h in range(13):
		dp[i + 1][h] %= 1000000007
print(dp[n][5])


S = input().strip()[::-1]
mod = 10 ** 9 + 7
n = len(S)
d = [[0] * 13 for _ in range(n + 1)]
d[0][0] = 1
b = 1
for i in range(n):
	for k in range(13):
		for j in range(10) if S[i] == '?' else [int(S[i])]:
			d[i + 1][(k + j * b) % 13] += d[i][k]
			d[i + 1][(k + j * b) % 13] %= mod
	b = b * 10 % 13
print(d[n][5])


def solve(S):
	N = len(S)
	MOD = 1000000007
	dp = [0] * 13
	dp[0] = 1
	for i in range(N):
		tmp = [0] * 13
		c = -1 if S[i] == '?' else int(S[i])
		for j in range(10):
			if c != -1 and c != j:
				continue
			for k in range(13):
				tmp[(j + k * 10) % 13] += dp[k]
		for j in range(13):
			dp[j] = tmp[j] % MOD
	return dp[5]
print(solve(input()))


s = input()
dp = [0] * 13
dp[0] = 1
for c in s:
	new = [0] * 13
	if c == '?':
		for n in range(10):
			for i in range(13):
				new[(i * 10 + n) % 13] += dp[i]
	else:
		n = int(c)
		for i in range(13):
			new[(i * 10 + n) % 13] += dp[i]
	for i in range(13):
		new[i] %= 10 ** 9 + 7
	dp = new
print(dp[5])


(mod1, mod2) = (10 ** 9 + 7, 998244353)
mod = mod1
dp = [0] * 13
dp[0] = 1
for i in input():
	if i == '?':
		dp = [sum((dp[4 * (j - k) % 13] for k in range(10))) % mod for j in range(13)]
	else:
		x = int(i)
		dp = [dp[4 * (j - x) % 13] for j in range(13)]
print(dp[5])


ss = list(input())
MOD = 10 ** 9 + 7
dp = [[0 for _ in range(13)] for _ in range(len(ss) + 1)]
dp[0][0] = 1
for (i, s) in enumerate(ss):
	if s == '?':
		for j in range(10):
			for k in range(13):
				dp[i + 1][(k * 10 + j) % 13] += dp[i][k] % MOD
	else:
		for k in range(13):
			dp[i + 1][(k * 10 + int(s)) % 13] += dp[i][k] % MOD
print(dp[-1][5] % MOD)


import numpy as np

def main():
	n = 13
	mod = 1000000007
	r = 5
	in_str = input()
	amari_l = amari_list(n)
	amari_m = amari_matrix(n, amari_l)
	ans_list = initial(in_str[-1:], n)
	for (i, s) in enumerate(reversed(in_str)):
		if i == 0:
			continue
		if s == '?':
			ans_list = np.dot(ans_list, amari_m[i % len(amari_m)]) % mod
		else:
			t = int(s) * amari_l[i % len(amari_l)] % n
			ans_list = np.roll(ans_list, t)
	print(int(ans_list[r] % mod))

def initial(s, n):
	if s == '?':
		return np.array([1 if i < 10 else 0 for i in range(n)], dtype='int64')
	else:
		return np.array([1 if i == int(s) else 0 for i in range(n)], dtype='int64')

def shift(n, r):
	return np.array([[1 if (i - j + r) % n == 0 else 0 for j in range(n)] for i in range(n)])

def amari_list(n):
	ret = []
	for i in range(n + 1):
		r = 10 ** i % n
		if r in ret:
			return ret
		else:
			ret.append(r)

def amari_matrix(n, amari_list):
	ret = np.zeros((len(amari_list), n, n))
	for (i, j) in enumerate(amari_list):
		tmp = np.zeros((n, n))
		for k in range(10):
			tmp += shift(n, j * k % n)
		ret[i] = tmp
	return ret

def __starting_point():
	main()
__starting_point()


MOD = 10 ** 9 + 7
S = input()
cur = [0] * 13
cur[0] = 1
r = 1
for i in range(len(S)):
	s = S[-(i + 1)]
	if s == '?':
		digits = range(10)
	else:
		digits = [int(s)]
	prev = cur
	cur = [0] * 13
	for m in range(13):
		for d in digits:
			cur[(m + r * d) % 13] += prev[m]
	for m in range(13):
		cur[m] %= MOD
	r = 10 * r % 13
print(cur[5])


import math
import heapq
import bisect
MOD = 10 ** 9 + 7
S = input()
ans = [0] * 13
ans[0] = 1
for c in S:
	dp = [0] * 13
	for i in range(13):
		dp[i * 10 % 13] = ans[i] % MOD
	dp += dp
	if c == '?':
		for i in range(13):
			ans[i] = sum(dp[i + 4:i + 14])
	else:
		for i in range(13):
			ans[i] = dp[i + 13 - int(c)]
print(ans[5] % MOD)


s = input()
l = len(s)
mod = 10 ** 9 + 7
dp = [[0 for j in range(13)] for i in range(l)]
if s[0] == '?':
	dp[0] = [1] * 10 + [0] * 3
else:
	dp[0][int(s[0])] = 1
for i in range(1, l):
	if s[i] == '?':
		for j in range(10):
			for k in range(13):
				dp[i][(k * 10 + j) % 13] += dp[i - 1][k] % mod
	else:
		for k in range(13):
			dp[i][(k * 10 + int(s[i])) % 13] += dp[i - 1][k] % mod
print(dp[-1][5] % mod)


S = input()
dp = [[0] * 13 for i in range(len(S) + 1)]
dp[0][0] = 1
mod = 10 ** 9 + 7
for i in range(len(S)):
	if S[i] == '?':
		for j in range(13):
			for k in range(10):
				dp[i + 1][(j * 10 + k) % 13] = (dp[i + 1][(j * 10 + k) % 13] + dp[i][j]) % mod
	else:
		k = int(S[i])
		for j in range(13):
			dp[i + 1][(j * 10 + k) % 13] = (dp[i + 1][(j * 10 + k) % 13] + dp[i][j]) % mod
print(dp[len(S)][5])


def main():
	s = input()
	mod = 10 ** 9 + 7
	table1 = [0] * 13
	table2 = [0] * 13
	table1[0] = 1
	pre = [[(10 * i + j) % 13 for j in range(10)] for i in range(13)]
	for l in s:
		for i in range(13):
			q = table1[i] % mod
			if q == 0:
				continue
			if l == '?':
				for k in pre[i]:
					table2[k] += q
			else:
				k = (10 * i + int(l)) % 13
				table2[k] += q
		table1 = table2
		table2 = [0] * 13
	print(table1[5] % mod)

def __starting_point():
	main()
__starting_point()


N = input()[::-1]
iv = 1
MOD = 10 ** 9 + 7
dp = [0] * 13
dp[0] = 1
ls = [0] * 13
for i in range(len(N)):
	x = N[i]
	if x == '?':
		for j in range(13):
			for h in range(10):
				ls[(h * iv + j) % 13] += dp[j]
	else:
		x = int(x)
		for j in range(13):
			ls[(j + x * iv) % 13] += dp[j]
	for j in range(13):
		dp[j] = ls[j] % MOD
		ls[j] = 0
	iv *= 10
	iv %= 13
print(dp[5])


s = input()
n = len(s)
mod = 10 ** 9 + 7
dp = [13 * [0] for _ in range(n)]
if s[0] == '?':
	dp[0] = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0]
else:
	dp[0][int(s[0])] = 1
for i in range(1, n):
	if s[i] != '?':
		k = int(s[i])
		for j in range(13):
			dp[i][(j * 10 + k) % 13] += dp[i - 1][j]
	else:
		for j in range(13):
			for k in range(10):
				dp[i][(j * 10 + k) % 13] += dp[i - 1][j]
	for j in range(13):
		dp[i][j] %= mod
print(dp[-1][5])


S = input()[::-1]
l = len(S)
a = 1
m = 10 ** 9 + 7
dp = [1] + [0] * 12
for d in S:
	dp2 = [0] * 13
	if d == '?':
		for j in range(13):
			for k in range(10):
				dp2[(j + k * a) % 13] += dp[j] % m
	else:
		for j in range(13):
			dp2[(j + int(d) * a) % 13] = dp[j]
	dp = dp2
	a = a * 10 % 13 if a != 1 else 10
print(dp[5] % m)


MOD = 10 ** 9 + 7
S = input()
N = len(S)
if N == 1:
	if S == '?' or int(S) == 5:
		print(1)
	else:
		print(0)
	return
if S[0] == '?':
	x = [1] * 10 + [0] * 3
else:
	x = [0] * 13
	x[int(S[0])] = 1
for i in range(1, N):
	if S[i] == '?':
		tmp = sum(x)
		x = [tmp - x[4] - x[8] - x[12], tmp - x[3] - x[8] - x[12], tmp - x[3] - x[7] - x[12], tmp - x[3] - x[7] - x[11], tmp - x[2] - x[7] - x[11], tmp - x[2] - x[6] - x[11], tmp - x[2] - x[6] - x[10], tmp - x[1] - x[6] - x[10], tmp - x[1] - x[5] - x[10], tmp - x[1] - x[5] - x[9], tmp - x[0] - x[5] - x[9], tmp - x[0] - x[4] - x[9], tmp - x[0] - x[4] - x[8]]
	elif S[i] == '0':
		x = [x[0], x[4], x[8], x[12], x[3], x[7], x[11], x[2], x[6], x[10], x[1], x[5], x[9]]
	elif S[i] == '1':
		x = [x[9], x[0], x[4], x[8], x[12], x[3], x[7], x[11], x[2], x[6], x[10], x[1], x[5]]
	elif S[i] == '2':
		x = [x[5], x[9], x[0], x[4], x[8], x[12], x[3], x[7], x[11], x[2], x[6], x[10], x[1]]
	elif S[i] == '3':
		x = [x[1], x[5], x[9], x[0], x[4], x[8], x[12], x[3], x[7], x[11], x[2], x[6], x[10]]
	elif S[i] == '4':
		x = [x[10], x[1], x[5], x[9], x[0], x[4], x[8], x[12], x[3], x[7], x[11], x[2], x[6]]
	elif S[i] == '5':
		x = [x[6], x[10], x[1], x[5], x[9], x[0], x[4], x[8], x[12], x[3], x[7], x[11], x[2]]
	elif S[i] == '6':
		x = [x[2], x[6], x[10], x[1], x[5], x[9], x[0], x[4], x[8], x[12], x[3], x[7], x[11]]
	elif S[i] == '7':
		x = [x[11], x[2], x[6], x[10], x[1], x[5], x[9], x[0], x[4], x[8], x[12], x[3], x[7]]
	elif S[i] == '8':
		x = [x[7], x[11], x[2], x[6], x[10], x[1], x[5], x[9], x[0], x[4], x[8], x[12], x[3]]
	elif S[i] == '9':
		x = [x[3], x[7], x[11], x[2], x[6], x[10], x[1], x[5], x[9], x[0], x[4], x[8], x[12]]
	x = [x[j] % MOD for j in range(13)]
print(x[5])


import numpy as np

def main():
	S = {i: s for (i, s) in enumerate(input()[::-1])}
	MOD = 10 ** 9 + 7
	DP_table = np.zeros(13).astype(np.int64)
	digit = S[0]
	if digit == '?':
		for i in range(10):
			DP_table[i] = 1
	else:
		DP_table[int(digit)] = 1
	transition_matrixes = {}
	for multiplier in range(13):
		for digit in range(10):
			transition_matrix = np.zeros((13, 13)).astype(np.int64)
			for k in range(13):
				transition_matrix[(digit * multiplier + k) % 13, k] = 1
			transition_matrixes[multiplier, digit] = transition_matrix
	transition_matrixes2 = {}
	for multiplier in range(13):
		transition_matrixes2[multiplier] = np.zeros((13, 13)).astype(np.int64)
		for digit in range(10):
			transition_matrixes2[multiplier] += transition_matrixes[multiplier, digit]
	multiplier = 1
	for i in range(1, len(S)):
		multiplier = multiplier * 10 % 13
		digit = S[i]
		if digit == '?':
			transition_matrix = transition_matrixes2[multiplier]
		else:
			transition_matrix = transition_matrixes[multiplier, int(digit)]
		DP_table = np.dot(transition_matrix, DP_table)
		DP_table %= MOD
	print(int(DP_table[5]))

def __starting_point():
	main()
__starting_point()


mo = 10 ** 9 + 7
t = input()[::-1]
dp = [0] * 13
dp[0] = 1
for d in range(len(t)):
	p = [0] * 13
	if t[d] == '?':
		for x in range(10):
			r = int(x) * pow(10, d, 13)
			for i in range(13):
				p[(i + r) % 13] += dp[i]
	else:
		r = int(t[d]) * pow(10, d, 13)
		for i in range(13):
			p[(i + r) % 13] = dp[i]
	dp = [j % mo for j in p]
print(dp[5] % mo)


MOD = 10 ** 9 + 7
s = input()
sl = list(s)
n = len(s)
dsl = {i: sl[i] for i in range(n)}
dp = {i: [0] * 13 for i in range(n + 1)}
dp[0][0] = 1
for i in range(n):
	for k in range(10):
		if dsl[i] != '?' and dsl[i] != str(k):
			continue
		for j in range(13):
			dp[i + 1][(j * 10 + k) % 13] += dp[i][j] % MOD
print(dp[n][5] % MOD)


M = 10 ** 9 + 7
a = [1] + [0] * 12
p = 1
for c in reversed(input()):
	if c == '?':
		b = a[:]
		for j in range(-p, -p * 10, -p):
			j %= 13
			a = [sum(x) % M for x in zip(a, b[j:] + b[:j])]
	elif c > '0':
		j = -p * int(c) % 13
		a = a[j:] + a[:j]
	p = p * 10 % 13
print(a[5])


S = input()
N = len(S)
MOD = 10 ** 9 + 7
dp = [[0] * 13 for _ in range(N + 1)]
dp[0][0] = 1
for i in range(N):
	c = int(S[i]) if S[i] != '?' else -1
	for j in range(10):
		if c == -1 or c == j:
			for ki in range(13):
				dp[i + 1][(ki * 10 + j) % 13] += dp[i][ki]
	for j in range(13):
		dp[i + 1][j] %= MOD
ans = dp[N][5]
print(ans)


S = input()
N = len(S)
dp = [[0 for _ in range(13)] for _ in range(10 ** 5 + 1)]
mod = 10 ** 9 + 7
dp[0][0] = 1
for i in range(N):
	s = S[i]
	for j in range(10):
		if s != '?' and s != str(j):
			continue
		for r in range(13):
			dp[i + 1][(r * 10 + j) % 13] += dp[i][r]
	for j in range(13):
		dp[i + 1][j] %= mod
print(dp[N][5])


s = input()
n = len(s)
v = [[0] * 13 for i in range(n + 1)]
v[0][0] = 1
m = 10 ** 9 + 7
for i in range(n):
	for j in range(13):
		for k in range(10):
			x = (10 * j + k) % 13
			v[i + 1][x] = (v[i + 1][x] + (1 if s[i] == '?' or s[i] == str(k) else 0) * v[i][j]) % m
print(v[n][5])


inf = 10 ** 9 + 7
s = input()
r = [[(j - k) * 9 % 13 for j in range(10)] for k in range(13)]
d = [1] + [0] * 12
for c in s:
	d = [sum((d[j] for j in k)) % inf for k in r] if c > '9' else [d[(int(c) - k) * 9 % 13] for k in range(13)]
print(d[5])


r = range
d = [1] + [0] * 12
for s in input():
	p = [0] * 13
	for j in r(13):
		for k in ([s], r(10))[s > '9']:
			t = (j * 10 + int(k)) % 13
			p[t] += d[j]
			p[t] %= 10 ** 9 + 7
	d = p
print(d[5])


s = str(input())
mod = 10 ** 9 + 7
n = len(s)
if s[0] == '?':
	ans = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0]
else:
	ans = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
	ans[int(s[0])] = 1
for i in s[1:]:
	dp = [0] * 13
	for j in range(13):
		dp[j * 10 % 13] = ans[j] % mod
	dp += dp
	if i == '?':
		for j in range(13):
			ans[j] = sum(dp[j + 4:j + 14])
	else:
		for j in range(13):
			ans[j] = dp[j + 13 - int(i)]
print(ans[5] % mod)


mod = 10 ** 9 + 7
s = input()
dp1 = [1] + [0] * 12
for i in range(len(s)):
	dp2 = [0] * 13
	if s[i] != '?':
		p = int(s[i])
		for j in range(13):
			dp2[(j * 10 + p) % 13] += dp1[j]
	else:
		for p in range(10):
			for j in range(13):
				dp2[(j * 10 + p) % 13] += dp1[j]
	dp1 = [dp2[j] % mod for j in range(13)]
print(dp1[5])


import numpy as np
s = input()
A = []
for i in range(6):
	m = [-(j * 10 ** i % 13) % 13 for j in range(10)]
	tmp = []
	for j in m:
		tmp.append([[1 if (k - l) % 13 == j else 0 for k in range(13)] for l in range(13)])
	tmp.append([[1 if (k - l) % 13 in m else 0 for k in range(13)] for l in range(13)])
	A.append(tmp)
A = np.array(A)
dp = np.zeros(13, dtype=int)
dp[0] = 1
m = 1
for (ind, i) in enumerate(reversed(s)):
	i = int(i) if i != '?' else 10
	tmp = np.dot(A[ind % 6, i, :, :], dp)
	dp = tmp % (10 ** 9 + 7)
print(dp[5])


d = [0] * 13
d[0] = 1
s = input()
for (k, t) in enumerate(s[::-1]):
	if t == '?':
		d2 = [0] * 13
		for i in range(10):
			u = i * pow(10, k, 13)
			for i in range(13):
				d2[(i + u) % 13] += d[i]
	else:
		u = int(t) * pow(10, k, 13)
		d2 = [0] * 13
		for i in range(13):
			d2[(i + u) % 13] += d[i]
	for i in range(13):
		d[i] = d2[i] % (10 ** 9 + 7)
print(d[5])


s = input()
MOD = 10 ** 9 + 7
dp = [[0 for i in range(13)] for i in range(len(s) + 1)]
dp[0][0] = 1
for i in range(len(s)):
	if s[i] == '?':
		for k in range(10):
			for j in range(13):
				dp[i + 1][(j * 10 + k) % 13] = (dp[i + 1][(j * 10 + k) % 13] + dp[i][j]) % MOD
	else:
		t = int(s[i])
		for j in range(13):
			dp[i + 1][(j * 10 + t) % 13] = (dp[i + 1][(j * 10 + t) % 13] + dp[i][j]) % MOD
print(dp[len(s)][5])


mod = 1000000007
S = list(input())
n = len(S)
dp = [[0] * 13 for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
	s = S[i]
	for j in range(13):
		if s == '?':
			for k in range(10):
				dp[i + 1][(j * 10 + k) % 13] += dp[i][j]
		else:
			dp[i + 1][(j * 10 + int(s)) % 13] += dp[i][j]
		dp[i + 1][j] %= mod
print(dp[n][5] % mod)


mod = 10 ** 9 + 7
s = [x for x in input()]
n = len(s)
dp = [[0 for i in range(13)] for j in range(n + 1)]
dp[0][0] = 1
for i in range(n):
	for j in range(10):
		if s[i] != '?' and s[i] != str(j):
			continue
		for k in range(13):
			dp[i + 1][(k * 10 + j) % 13] += dp[i][k]
	for j in range(13):
		dp[i + 1][j] = dp[i + 1][j] % mod
print(dp[n][5])


import sys, math, copy

def main():
	input = sys.stdin.readline
	S = ''.join(reversed(input().strip()))
	dp = [0] * 13
	dp_ = [0] * 13
	mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
	list10 = list(range(10))
	list13 = list(range(13))
	divisor = 10 ** 9 + 7
	dp_[0] = 1
	mul = 1
	for i in range(len(S)):
		s = S[i]
		if s == '?':
			for d in list10:
				m = mod13_list[d * mul]
				for pm in list13:
					dp[mod13_list[pm + m]] += dp_[pm]
		else:
			si = int(s)
			m = mod13_list[si * mul]
			for pm in list13:
				dp[mod13_list[pm + m]] = dp_[pm]
		for j in list13:
			dp_[j] = dp[j] % divisor
			dp[j] = 0
		mul = mod13_list[mul * 10]
	print(dp_[5])

def __starting_point():
	main()
__starting_point()


s = input()
l = len(s)
MOD = 10 ** 9 + 7
dp = [[0] * 13 for _ in range(100005)]
dp[0][0] = 1
for i in range(l):
	c = -1 if s[i] == '?' else int(s[i])
	for j in range(10):
		if c != -1 and c != j:
			continue
		for r in range(13):
			dp[i + 1][(10 * r + j) % 13] += dp[i][r]
	for k in range(13):
		dp[i + 1][k] %= MOD
print(dp[l][5])


S = input()
MOD = 10 ** 9 + 7
M = 13
dp = [0] * M
dp[0] = 1
for s in S:
	newDp = [0] * M
	if s == '?':
		for s in range(10):
			for m in range(M):
				newDp[(m * 10 + s) % M] += dp[m]
	else:
		s = int(s)
		for m in range(M):
			newDp[(m * 10 + s) % M] += dp[m]
	dp = newDp
	for m in range(M):
		dp[m] %= MOD
print(newDp[5] % MOD)


d = [0] * 13
d[0] = 1
for c in input():
	e = [0] * 13
	for k in range(10) if c > '>' else [int(c)]:
		for j in range(13):
			t = (j * 10 + k) % 13
			e[t] += d[j]
			e[t] %= 10 ** 9 + 7
	d = e
print(d[5])


def main():
	S = [int(i) if i != '?' else -1 for i in input()]
	s = len(S)
	mod = 10 ** 9 + 7
	dp = [[0] * 13 for _ in range(s)]
	table = [[0] * 10 for _ in range(13)]
	for i in range(13):
		for j in range(10):
			table[i][j] = (i * 10 + j) % 13
	table2 = [[] for _ in range(13)]
	for i in range(13):
		for j in range(10):
			table2[table[i][j]].append(i)
	t = set(range(13))
	table2 = [t - set(i) for i in table2]
	if S[0] == -1:
		for i in range(10):
			dp[0][i] += 1
	else:
		dp[0][S[0] % 13] += 1
	for i in range(1, s):
		if S[i] == -1:
			temp = sum(dp[i - 1])
			for j in range(13):
				dp[i][j] = temp
				for k in table2[j]:
					dp[i][j] -= dp[i - 1][k]
				dp[i][j] %= mod
		else:
			for j in range(13):
				dp[i][table[j][S[i]]] = dp[i - 1][j]
	print(dp[-1][5] % mod)

def __starting_point():
	main()
__starting_point()


S = str(input())
ans = [0] * 13
ans[0] = 1
MOD = 10 ** 9 + 7
for i in S:
	dp = [0] * 13
	for j in range(13):
		dp[j * 10 % 13] = ans[j] % MOD
	dp += dp
	if i == '?':
		for j in range(13):
			ans[j] = sum(dp[j + 4:j + 14])
	else:
		for j in range(13):
			ans[j] = dp[j + 13 - int(i)]
print(ans[5] % MOD)


MOD = 1000000007
S = input()[::-1]
N = len(S)
pows = list(range(10))
dp = [[0] * 13 for _ in range(N + 1)]
dp[0][0] = 1
for i in range(N):
	for src in range(13):
		for (j, p) in enumerate(pows):
			if S[i] == '?' or int(S[i]) == j:
				dst = (src + p) % 13
				dp[i + 1][dst] = (dp[i + 1][dst] + dp[i][src]) % MOD
	for i in range(10):
		pows[i] = pows[i] * 10 % 13
print(dp[N][5])


S = input()
dp = 13 * [0]
dp[0] = 1
mod = 10 ** 9 + 7
for s in S:
	if s == '?':
		dp = [sum((dp[4 * (j - i) % 13] for i in range(10))) % mod for j in range(13)]
	else:
		dp = [dp[4 * (j - int(s)) % 13] for j in range(13)]
print(dp[5])


import numpy as np
MOD = 10 ** 9 + 7
S = [int(x) if x != '?' else -1 for x in input()]
N = len(S)
r = [0] * 13
s = S[0]
if s != -1:
	r[s] = 1
else:
	for i in range(10):
		r[i] = 1
for i in range(1, N):
	dp = [0] * 26
	for j in range(13):
		dp[j * 10 % 13] += r[j] % MOD
	dp[13:26] = dp[0:13]
	r = [0] * 13
	s = S[i]
	if s == -1:
		w = sum(dp[4:14])
		for j in range(13):
			r[j] += w
			w += dp[j + 1] - dp[j + 4]
	else:
		for j in range(13):
			r[j] += dp[13 - s + j]
print(r[5] % MOD)


def main():
	MOD = 10 ** 9 + 7
	s = input()
	r = [0] * 13
	r[0] = 1
	p = 1
	for c in reversed(s):
		if c == '?':
			tank = []
			for x in range(10):
				x = x * p % 13
				tank.append(r[13 - x:] + r[:13 - x])
			r = list(map(sum, list(zip(*tank))))
			(*r,) = [x % MOD for x in r]
		else:
			x = int(c)
			x = x * p % 13
			r = r[13 - x:] + r[:13 - x]
		p = p * 10 % 13
	print(r[5])

def __starting_point():
	main()
__starting_point()


MOD = 10 ** 9 + 7

def main(s):
	reminder = [[(j - k) * 9 % 13 for j in range(10)] for k in range(13)]
	dp = [1] + [0] * 12
	for char in s:
		if char == '?':
			dp = [sum((dp[j] for j in k)) % MOD for k in reminder]
		else:
			dp = [dp[(int(char) - k) * 9 % 13] for k in range(13)]
	return dp[5]
S = input()
print(main(S))


m = 10 ** 9 + 7
s = input()
d = [1] + [0] * 12
for i in range(len(s)):
	if s[i] == '?':
		d = [sum((d[(j - k) * 4 % 13] for k in range(10))) % m for j in range(13)]
	else:
		d = [d[(j - int(s[i])) * 4 % 13] % m for j in range(13)]
print(d[5])


mod = 10 ** 9 + 7
S = input()
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
for (i, s) in enumerate(S):
	c = -1 if s == '?' else int(s)
	for j in range(10):
		if c != -1 and c != j:
			continue
		for k in range(13):
			dp[i + 1][(k * 10 + j) % 13] += dp[i][k]
	for j in range(13):
		dp[i + 1][j] %= mod
print(dp[len(S)][5])


z = 10
m = z ** 9 + 7
k = 13
t = input()[::-1]
dp = [0] * k
dp[0] = 1
for d in range(len(t)):
	p = [0] * k
	f = t[d] == '?'
	for i in range(k):
		l = pow(z, d, k)
		for x in range(1 + f * 9):
			r = l * int(x if f else t[d])
			p[(i + r) % k] += dp[i]
	dp = [j % m for j in p]
print(dp[5] % m)


S = input()
n = len(S)
l = [0] * 13
l[0] = 1
pr = 10 ** 9 + 7
for i in range(n):
	a = [0] * 13
	p = pow(10, i, 13)
	s = S[-i - 1]
	if s == '?':
		for j in range(10):
			for k in range(13):
				a[(k + p * j) % 13] += l[k] % pr
	else:
		for k in range(13):
			a[(k + p * int(s)) % 13] += l[k] % pr
	l = a
print(l[5] % pr)


import sys
input = sys.stdin.readline
S = list(input().rstrip('\n'))
kake10 = [0, 10, 7, 4, 1, 11, 8, 5, 2, 12, 9, 6, 3]
now = {0: 1, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0, 10: 0, 11: 0, 12: 0}
for i in S:
	now = {kake10[x]: now[x] for x in range(13)}
	if i == '?':
		now2 = {x: sum((now[(x + y) % 13] for y in range(4, 14))) % 1000000007 for x in range(13)}
		now = now2
	else:
		a = int(i)
		now = {(x + a) % 13: now[x] for x in range(13)}
print(now[5])


S = input()
g = 10 ** 9 + 7
x = 1
DP = [[0] * 13 for _ in range(2)]
DP[0][0] = 1
for i in range(len(S)):
	for j in range(13):
		DP[1][j] = DP[0][j] % g
		DP[0][j] = 0
	for j in range(13):
		if S[i] == '?':
			for k in range(10):
				DP[0][(j * 10 + k) % 13] += DP[1][j]
		else:
			DP[0][(j * 10 + int(S[i])) % 13] += DP[1][j]
print(DP[0][5] % g)


S = input()
a = [0] * 13
a[0] = 1
for c in S:
	dp = [0] * 13
	for i in range(13):
		dp[i * 10 % 13] = a[i] % (10 ** 9 + 7)
	dp += dp
	if c == '?':
		for i in range(13):
			a[i] = sum(dp[i + 4:i + 14])
	else:
		for i in range(13):
			a[i] = dp[i + 13 - int(c)]
print(a[5] % (10 ** 9 + 7))


X = input()
MOD = 10 ** 9 + 7
M = 13
S = [0] * M
S[0] = 1
T = [0] * M

def calc(S, T, x):
	for i in range(M):
		T[(i * 10 + x) % M] += S[i]
	for i in range(M):
		T[i] %= MOD
zeros = [0] * M
for c in X:
	T[:] = zeros
	if c == '?':
		for x in range(10):
			calc(S, T, x)
	else:
		x = int(c)
		calc(S, T, x)
	(S, T) = (T, S)
print(S[5])


import sys

def main():
	s = str(input())
	l = len(s)
	ans = [0 for _ in range(13)]
	MOD = 10 ** 9 + 7
	ans[0] = 1
	for st in s:
		dp = [0 for _ in range(13)]
		for i in range(13):
			dp[10 * i % 13] = ans[i] % MOD
		dp += dp
		if st != '?':
			for i in range(13):
				num = int(st)
				ans[i] = dp[i + 13 - num]
		else:
			for i in range(13):
				ans[i] = sum(dp[i + 4:i + 14])
	print(ans[5] % MOD)

def __starting_point():
	main()
__starting_point()


M = 10 ** 9 + 7
r = [[(j - i) * 4 % 13 for i in range(10)] for j in range(13)]
d = [1] + [0] * 12
for c in input():
	if c > '9':
		d = [sum((d[i] for i in j)) % M for j in r]
	else:
		d = [d[(j - int(c)) * 4 % 13] for j in range(13)]
print(d[5])


S = input()
MOD = 10 ** 9 + 7
dp = [0] * 13
dp[0] = 1
for s in S:
	prev = dp
	dp = [0] * 13
	if s == '?':
		add = range(10)
	else:
		add = [int(s)]
	for i in range(13):
		for a in add:
			dp[(10 * i + a) % 13] += prev[i]
	dp = [x % MOD for x in dp]
print(dp[5])


S = input()
dp = [[0 for _ in range(13)] for _ in range(len(S))]
MOD = 10 ** 9 + 7
if S[0] == '?':
	for i in range(10):
		dp[0][i] = 1
else:
	dp[0][int(S[0])] += 1
for i in range(1, len(S)):
	cur_nums = [i for i in range(10)] if S[i] == '?' else [int(S[i])]
	for cur in cur_nums:
		for rem in range(13):
			dp[i][(10 * rem + cur) % 13] = (dp[i][(10 * rem + cur) % 13] + dp[i - 1][rem]) % MOD
print(dp[-1][5])


MOD = 1000000007
s = [int(x) if x != '?' else -1 for x in input()]
n = len(s)
r = [0] * 13
c = s[0]
if c != -1:
	r[c] = 1
else:
	for i in range(10):
		r[i] = 1
for i in range(1, n):
	dp = [0] * 26
	for j in range(13):
		dp[j * 10 % 13] += r[j] % MOD
	dp[13:26] = dp[0:13]
	c = s[i]
	r = [0] * 13
	if c == -1:
		w = sum(dp[4:14])
		for j in range(13):
			r[j] += w
			w = w + dp[j + 1] - dp[4 + j]
	else:
		for j in range(13):
			r[j] += dp[13 - c + j]
print(r[5] % MOD)


import numpy as np
s = input()
p = np.array([0] * 13)
p[0] = 1
amari = [[0] * 13 for _ in range(13)]
for j in range(10):
	for i in range(13):
		amari[i][(i * 10 + j) % 13] += 1
M = np.array(amari)
for si in range(len(s)):
	a = np.array([0] * 13)
	if s[si] == '?':
		a = np.dot(p, M)
	else:
		c = int(s[si])
		for i in range(13):
			a[(i * 10 + c) % 13] += p[i]
	p = np.mod(a, 1000000007)
print(p[5])


x = 1000000007
S = input()
S = [int(s) if s != '?' else s for s in S]
dp = [[0 for j in range(13)] for i in range(len(S) + 1)]
dp[0][0] = 1
for (i, s) in enumerate(S):
	for j in range(10):
		if s != '?' and s != j:
			continue
		for k in range(13):
			dp[i + 1][(10 * k + j) % 13] += dp[i][k] % x
print(int(dp[-1][5] % x))


modarr61 = [76924, 76923, 76923, 76923, 76923, 76923, 76923, 76923, 76923, 76923, 76923, 76923, 76923]
modarr51 = [7693, 7692, 7692, 7692, 7693, 7692, 7692, 7693, 7692, 7692, 7693, 7692, 7692]
modarr52 = [7693, 7693, 7692, 7692, 7692, 7693, 7692, 7692, 7692, 7693, 7692, 7692, 7692]
modarr53 = [7693, 7692, 7692, 7692, 7692, 7692, 7692, 7692, 7692, 7692, 7693, 7693, 7693]
modarr54 = [7693, 7692, 7692, 7693, 7692, 7692, 7693, 7692, 7692, 7693, 7692, 7692, 7692]
modarr55 = [7693, 7692, 7692, 7692, 7693, 7692, 7692, 7692, 7693, 7692, 7692, 7692, 7693]
modarr56 = [7693, 7693, 7693, 7693, 7692, 7692, 7692, 7692, 7692, 7692, 7692, 7692, 7692]
modarr41 = [770, 769, 769, 769, 769, 770, 769, 769, 769, 770, 769, 769, 769]
modarr42 = [769, 769, 769, 769, 770, 769, 769, 770, 769, 769, 770, 769, 769]
modarr43 = [770, 769, 769, 769, 769, 769, 769, 769, 769, 769, 769, 770, 770]
modarr44 = [772, 768, 768, 771, 769, 768, 770, 770, 768, 769, 771, 768, 768]
modarr45 = [769, 770, 769, 769, 769, 770, 769, 769, 769, 770, 769, 769, 769]
modarr46 = [770, 769, 769, 770, 769, 769, 770, 769, 769, 769, 769, 769, 769]
modarr47 = [769, 769, 769, 769, 770, 769, 769, 769, 770, 769, 769, 769, 770]
modarr48 = [772, 769, 768, 768, 771, 770, 768, 768, 770, 771, 768, 768, 769]
modarr49 = [769, 769, 769, 769, 769, 769, 769, 769, 769, 769, 770, 770, 770]
modarr410 = [770, 769, 769, 769, 770, 769, 769, 769, 770, 769, 769, 769, 769]
modarr411 = [770, 769, 769, 769, 769, 769, 769, 770, 769, 769, 770, 769, 769]
modarr412 = [769, 770, 770, 770, 769, 769, 769, 769, 769, 769, 769, 769, 769]
modarr413 = [772, 771, 770, 769, 768, 768, 768, 768, 768, 768, 769, 770, 771]
modarr414 = [769, 769, 769, 770, 769, 769, 770, 769, 769, 770, 769, 769, 769]
modarr415 = [770, 770, 770, 769, 769, 769, 769, 769, 769, 769, 769, 769, 769]
modarr31 = [77, 76, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77]
modarr32 = [77, 77, 77, 77, 76, 78, 77, 76, 77, 78, 76, 77, 77]
modarr33 = [79, 76, 76, 78, 77, 76, 77, 78, 76, 76, 79, 76, 76]
modarr34 = [77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 76, 77, 77]
modarr35 = [79, 76, 76, 76, 79, 77, 76, 76, 78, 78, 76, 76, 77]
modarr36 = [76, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77]
modarr37 = [77, 76, 77, 77, 77, 76, 77, 77, 77, 76, 77, 78, 78]
modarr38 = [77, 77, 77, 76, 78, 77, 76, 77, 78, 76, 77, 77, 77]
modarr39 = [79, 77, 76, 76, 78, 78, 76, 76, 77, 79, 76, 76, 76]
modarr310 = [77, 77, 77, 77, 77, 77, 77, 77, 77, 76, 77, 77, 77]
modarr311 = [77, 77, 77, 77, 76, 77, 77, 77, 77, 77, 77, 77, 77]
modarr312 = [77, 76, 76, 76, 77, 77, 77, 78, 77, 77, 78, 77, 77]
modarr313 = [79, 79, 78, 77, 76, 76, 76, 76, 76, 76, 76, 77, 78]
modarr314 = [79, 76, 76, 79, 76, 76, 78, 77, 76, 77, 78, 76, 76]
modarr315 = [76, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77]
modarr316 = [77, 77, 77, 78, 77, 77, 78, 77, 77, 77, 76, 76, 76]
modarr317 = [77, 77, 77, 76, 77, 77, 77, 77, 77, 77, 77, 77, 77]
modarr318 = [77, 78, 78, 77, 76, 77, 77, 77, 76, 77, 77, 77, 76]
modarr319 = [79, 78, 77, 76, 76, 76, 76, 76, 76, 76, 77, 78, 79]
modarr320 = [77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 76]
modarr21 = [8, 7, 8, 8, 7, 8, 8, 7, 8, 8, 7, 8, 8]
modarr22 = [7, 7, 8, 8, 8, 7, 8, 8, 8, 7, 8, 8, 8]
modarr23 = [10, 7, 7, 7, 9, 8, 7, 7, 8, 9, 7, 7, 7]
modarr24 = [7, 8, 8, 7, 8, 8, 7, 8, 8, 7, 8, 8, 8]
modarr25 = [8, 7, 8, 8, 8, 7, 8, 8, 8, 7, 7, 8, 8]
modarr26 = [8, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8]
modarr27 = [7, 8, 8, 8, 7, 8, 8, 7, 8, 8, 7, 8, 8]
modarr28 = [10, 7, 7, 9, 7, 7, 8, 8, 7, 7, 9, 7, 7]
modarr29 = [7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 7, 7, 7]
modarr210 = [8, 8, 8, 7, 7, 8, 8, 8, 7, 8, 8, 8, 7]
modarr211 = [7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8]
modarr212 = [10, 9, 8, 7, 7, 7, 7, 7, 7, 7, 7, 8, 9]
modarr213 = [8, 8, 8, 7, 8, 8, 7, 8, 8, 7, 8, 8, 7]
modarr214 = [7, 8, 8, 8, 7, 8, 8, 8, 7, 8, 8, 8, 7]
modarr215 = [8, 8, 8, 8, 8, 8, 8, 8, 8, 7, 7, 7, 7]
modarr11 = [1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1]
modarr12 = [1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1]
modarr13 = [1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
modarr14 = [1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0]
modarr15 = [1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1]
modarr16 = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0]

def makemod(n):
	if n == 100000:
		return modarr11
	elif n == 10000:
		return modarr12
	elif n == 1000:
		return modarr13
	elif n == 100:
		return modarr14
	elif n == 10:
		return modarr15
	elif n == 1:
		return modarr16
	elif n == 110000:
		return modarr21
	elif n == 101000:
		return modarr22
	elif n == 100100:
		return modarr23
	elif n == 100010:
		return modarr24
	elif n == 100001:
		return modarr25
	elif n == 11000:
		return modarr26
	elif n == 10100:
		return modarr27
	elif n == 10010:
		return modarr28
	elif n == 10001:
		return modarr29
	elif n == 1100:
		return modarr210
	elif n == 1010:
		return modarr211
	elif n == 1001:
		return modarr212
	elif n == 110:
		return modarr213
	elif n == 101:
		return modarr214
	elif n == 11:
		return modarr215
	elif n == 111000:
		return modarr31
	elif n == 110100:
		return modarr32
	elif n == 110010:
		return modarr33
	elif n == 110001:
		return modarr34
	elif n == 101100:
		return modarr35
	elif n == 101010:
		return modarr36
	elif n == 101001:
		return modarr37
	elif n == 100110:
		return modarr38
	elif n == 100101:
		return modarr39
	elif n == 100011:
		return modarr310
	elif n == 11100:
		return modarr311
	elif n == 11010:
		return modarr312
	elif n == 11001:
		return modarr313
	elif n == 10110:
		return modarr314
	elif n == 10101:
		return modarr315
	elif n == 10011:
		return modarr316
	elif n == 1110:
		return modarr317
	elif n == 1101:
		return modarr318
	elif n == 1011:
		return modarr319
	elif n == 111:
		return modarr320
	elif n == 111100:
		return modarr41
	elif n == 111010:
		return modarr42
	elif n == 111001:
		return modarr43
	elif n == 110110:
		return modarr44
	elif n == 110101:
		return modarr45
	elif n == 110011:
		return modarr46
	elif n == 101110:
		return modarr47
	elif n == 101101:
		return modarr48
	elif n == 101011:
		return modarr49
	elif n == 100111:
		return modarr410
	elif n == 11110:
		return modarr411
	elif n == 11101:
		return modarr412
	elif n == 11011:
		return modarr413
	elif n == 10111:
		return modarr414
	elif n == 1111:
		return modarr415
	elif n == 111110:
		return modarr51
	elif n == 111101:
		return modarr52
	elif n == 111011:
		return modarr53
	elif n == 110111:
		return modarr54
	elif n == 101111:
		return modarr55
	elif n == 11111:
		return modarr56
s = input()
l = len(s)
if l % 6 != 0:
	s = '0' * (6 - l % 6) + s
	l += 6 - l % 6
mod = 10 ** 9 + 7
cnt = 0
dp = [[0] * 13 for _ in range(l // 6 + 1)]
for i in range(l - 1, -1, -6):
	num = 0
	qpos = 0
	for j in range(6):
		if s[i - j] == '?':
			qpos += 1 * 10 ** j
		else:
			num += int(s[i - j]) * 10 ** j
	if qpos == 0:
		tmod = [0] * 13
		tmod[num % 13] = 1
	elif qpos == 111111:
		tmod = modarr61
	else:
		tpos = num % 13
		tmod = makemod(qpos)
		tmod = tmod[-tpos:] + tmod[:-tpos]
	if cnt == 0:
		dp[1] = tmod
	else:
		for k in range(13):
			for l in range(13):
				dp[cnt + 1][(k + l) % 13] += tmod[k] * dp[cnt][l] % mod
	cnt += 1
print(dp[cnt][5] % mod)


s = list(input())
dp = [[0] * 13 for _ in range(100005)]
n = len(s)
res = 0
mod = 10 ** 9 + 7
dp[0][0] = 1
for i in range(n):
	c = int(s[i]) if s[i] != '?' else -1
	for j in range(10):
		if c != -1 and c != j:
			continue
		for k in range(13):
			dp[i + 1][(k * 10 + j) % 13] += dp[i][k]
	for j in range(13):
		dp[i + 1][j] %= mod
print(dp[n][5])


M = 10 ** 9 + 7
a = [1] + [0] * 12
b = (1, 10, 9, 12, 3, 4)
for (k, c) in enumerate(reversed(input())):
	p = b[k % 6]
	r = range(0, p * 10, p) if c == '?' else (p * int(c),)
	a = [sum((a[(i - j) % 13] for j in r)) % M for i in range(13)]
print(a[5])


s = list(input())
n = len(s)
dp = [[0] * 13 for i in range(n + 1)]
dp[0][0] = 1
for i in range(n):
	flag = 1 if s[i] == '?' else 0
	for a in range(10):
		if flag == 1 or s[i] == str(a):
			for j in range(13):
				dp[i + 1][(j * 10 + a) % 13] += dp[i][j]
	for j in range(13):
		dp[i + 1][j] %= 10 ** 9 + 7
print(dp[n][5])


import sys
s = sys.stdin.readline().strip()
MOD = 10 ** 9 + 7
mmap = []
for i in range(6):
	b = 10 ** i % 13
	mmap.append([[(b * i + j) % 13 for i in range(1, 10)] for j in range(13)])
dp = [0] * 13
dp[0] = 1
j = 0
for c in reversed(s):
	tmp = dp.copy()
	if c == '0':
		pass
	elif c == '?':
		bset = mmap[j]
		for (m, num) in enumerate(tmp):
			if num == 0:
				continue
			for idx in bset[m]:
				dp[idx] += num
		for i in range(13):
			dp[i] %= MOD
	else:
		b = mmap[j][0][int(c) - 1]
		for m in range(13):
			idx = (m + b) % 13
			dp[idx] = tmp[m]
	if j == 5:
		j = 0
	else:
		j += 1
print(dp[5])


S = input()
d = [0] * 13
d[0] = 1
for i in range(len(S)):
	n = [0] * 13
	for j in range(13):
		for k in range(10):
			n[(10 * j + k) % 13] += (1 if S[i] == '?' or int(S[i]) == k else 0) * d[j]
	for j in range(13):
		d[j] = n[j] % (10 ** 9 + 7)
print(d[5])


d = [1] + [0] * 12
for c in input():
	p = [0] * 13
	for j in range(13):
		for k in range(10):
			t = (j * 10 + k) % 13
			p[t] += d[j] * (c > '9' or k == int(c))
			p[t] %= 10 ** 9 + 7
	d = p
print(d[5])


d = [1] + [0] * 12
for c in input():
	d = [sum((d[(int(i) - k) * 9 % 13] for i in (c, range(10))[c > '9'])) % (10 ** 9 + 7) for k in range(13)]
print(d[5])


S = input()
mod = 10 ** 9 + 7
dp = [0] * 13
dp[0] = 1
for s in S:
	d = [0] * 13
	if s == '?':
		for i in range(13):
			for j in range(10):
				d[(10 * i + j) % 13] += dp[i]
	else:
		for i in range(13):
			d[(10 * i + int(s)) % 13] += dp[i]
	dp = [x % mod for x in d]
print(d[5] % mod)


import numpy as np
S = input()
mod = int(10 ** 9 + 7)
dp = np.zeros(13, dtype=int)
dp[0] = 1
M = np.zeros((13, 13), dtype=int)
for i in range(13):
	for d in range(10):
		M[i][(i * 10 + d) % 13] += 1
for s in S:
	ndp = np.zeros(13, dtype=int)
	if s == '?':
		ndp = np.dot(dp, M)
	else:
		d = int(s)
		for j in range(13):
			ndp[(j * 10 + d) % 13] += dp[j]
	dp = ndp % mod
print(dp[5])


MOD = 1000000007
m = 13
S = input()
start = int(S.replace('?', '0')) % m
dp = [0] * 13
dp[start] = 1
for (i, s) in enumerate(S[::-1]):
	nextDP = [0] * 13
	if s != '?':
		continue
	mul = pow(10, i, m)
	for j in range(10):
		for k in range(m):
			nextDP[(mul * j + k) % m] += dp[k]
			nextDP[(mul * j + k) % m] %= MOD
	dp = nextDP
print(dp[5])


S = input()
m = 13
d = [0] * m
d[0] = 1
for s in S:
	n = [0] * m
	for j in range(m):
		for k in range(10) if s == '?' else [int(s)]:
			n[(10 * j + k) % m] += d[j]
	d = [l % (10 ** 9 + 7) for l in n]
print(d[5])


s = input()
d = [0] * 13
d[0] = 1
for i in s:
	dnew = [0] * 13
	if i == '?':
		for j in range(10):
			for k in range(13):
				dnew[(10 * k + j) % 13] += d[k]
			for k in range(13):
				dnew[k] %= 10 ** 9 + 7
	else:
		for k in range(13):
			dnew[(10 * k + int(i)) % 13] += d[k]
		for k in range(13):
			dnew[k] %= 10 ** 9 + 7
	d = dnew
print(d[5])


s = input()
a = [0] * 13
a[0] = 1
for i in s:
	b = [0] * 13
	for (j, k) in enumerate(a):
		b[j * 10 % 13] += k
	a = b[:]
	b = [0] * 13
	if i == '?':
		for l in range(10):
			for (j, k) in enumerate(a):
				b[(j + l) % 13] += k
	else:
		for (j, k) in enumerate(a):
			b[(j + int(i)) % 13] += k
	a = [j % (10 ** 9 + 7) for j in b]
print(a[5] % (10 ** 9 + 7))


s = input()
l = len(s)
dp = [[0 for _ in range(13)] for _ in range(l + 1)]
dp[0][0] = 1
temp = [0] * 13
summ = 1
mod = 10 ** 9 + 7
for i in range(0, l):
	if s[i] != '?':
		for k in range(13):
			dp[i + 1][(k * 10 + int(s[i])) % 13] = dp[i][k]
	else:
		for k in range(13):
			temp[k * 10 % 13] = dp[i][k]
		excluded = temp[1] + temp[2] + temp[3]
		for k in range(13):
			dp[i + 1][k] = (summ - excluded) % mod
			excluded -= temp[(k + 1) % 13]
			excluded += temp[(k + 4) % 13]
		summ *= 10
		summ %= mod
print(dp[l][5])


MOD = 10 ** 9 + 7
S = input()
old = [0] * 13
old[0] = 1
n = 1
for c in S:
	dp = [0] * 13
	if c == '?':
		for j in range(10):
			for i in range(13):
				dp[(i * 10 + j) % 13] += old[i]
				dp[(i * 10 + j) % 13] %= MOD
	else:
		c = int(c)
		for i in range(13):
			dp[(i * 10 + c) % 13] += old[i]
			dp[(i * 10 + c) % 13] %= MOD
	old = [i for i in dp]
print(dp[5])


MOD = 10 ** 9 + 7
s = input()
n = len(s)
dp = [[0] * 13 for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
	for j in range(13):
		if s[i] == '?':
			for d in range(10):
				dp[i + 1][(10 * j + d) % 13] += dp[i][j]
				dp[i + 1][(10 * j + d) % 13] %= MOD
		else:
			dp[i + 1][(10 * j + int(s[i])) % 13] += dp[i][j]
print(dp[n][5])


MOD = 10 ** 9 + 7

def main():
	s = [int(in_i) if in_i != '?' else -1 for in_i in list(open(0).read())[:-1]]
	n = len(s)
	cnt = [0] * 13
	if s[0] == -1:
		for j in range(10):
			cnt[j] = 1
	else:
		cnt[s[0]] = 1
	for cur_s in s[1:]:
		dp = [0] * 26
		for i in range(13):
			dp[i * 10 % 13] = cnt[i] % MOD
		dp[13:] = dp[:13]
		if cur_s == -1:
			for i in range(13):
				cnt[i] = sum(dp[i + 4:i + 14])
		else:
			for i in range(13):
				cnt[i] = dp[i + 13 - cur_s]
	ans = cnt[5] % MOD
	print(ans)
	return ()

def __starting_point():
	main()
__starting_point()


S = input()
num_mod = 10 ** 9 + 7
dp = [1] + [0] * 12
for i in range(len(S)):
	nextdp = [0] * 13
	if S[i] == '?':
		for j in range(13):
			for k in range(10):
				nextdp[(j * 10 + k) % 13] += dp[j]
	else:
		for j in range(13):
			nextdp[(j * 10 + int(S[i])) % 13] += dp[j]
	for j in range(13):
		nextdp[j] %= num_mod
	dp = nextdp
print(dp[5])


S = list(input())
dp = [[0 for _ in range(13)] for _ in range(len(S) + 1)]
dp[0][0] = 1
for i in range(len(S)):
	a = 0
	if S[i] == '?':
		a = -1
	else:
		a = int(S[i])
	for j in range(10):
		if a != -1 and a != j:
			continue
		for k in range(13):
			dp[i + 1][(k * 10 + j) % 13] += dp[i][k]
	for k in range(13):
		dp[i + 1][k] %= 10 ** 9 + 7
print(dp[len(S)][5])


import numpy as np
import sys

def input():
	return sys.stdin.readline()[:-1]
MOD = 1000000007
S = [int(x) if x != '?' else -1 for x in input()]
n = len(S)
r = [0] * 13
s = S[0]
if s != -1:
	r[s] = 1
else:
	for i in range(10):
		r[i] = 1
for i in range(1, n):
	dp = [0] * 26
	for j in range(13):
		dp[j * 10 % 13] += r[j] % MOD
	dp[13:26] = dp[0:13]
	r = [0] * 13
	s = S[i]
	if s == -1:
		w = sum(dp[4:14])
		for j in range(13):
			r[j] += w
			w += dp[j + 1] - dp[j + 4]
	else:
		for j in range(13):
			r[j] += dp[13 - s + j]
print(r[5] % MOD)


MOD = 1000000007
s = [-1 if x == '?' else int(x) for x in input()]
n = len(s) + 1
dp = [0] * 13
dp[0] = 1
r = [[(j - i) * 4 % 13 for i in range(10)] for j in range(13)]
for (i, x) in enumerate(s):
	next_dp = [0] * 13
	if x == -1:
		next_dp = [sum((dp[i] for i in j)) for j in r]
	else:
		next_dp = [dp[j[x]] for j in r]
	dp = [k % MOD for k in next_dp]
print(dp[5])


s = input()[::-1]
p = [1] + [0] * 12
q = 1
t = [[i * k % 13 for i in range(10)] for k in range(13)]
for i in s:
	if i != '?':
		i = int(i)
		g = t[q][i]
		p = p[-g:] + p[:-g]
	else:
		d = [0] * 13
		for j in t[q]:
			r = p[-j:] + p[:-j]
			d = [(r[i] + d[i]) % (10 ** 9 + 7) for i in range(13)]
		p = d
	q = q * 10 % 13
print(p[5] % (10 ** 9 + 7))


S = input()
import numpy as np
M = 13
MOD = 10 ** 9 + 7
dp = np.zeros(M, dtype=np.int64)
dp[0] = 1
idx = np.zeros(M, dtype=np.int8)
window = np.ones(10, dtype=np.int8)
for i in range(M):
	idx[i * 10 % M] = i
for s in S:
	if s == '?':
		tdp = dp[idx]
		ndp = np.concatenate([tdp[4:], tdp])
		dp = np.convolve(ndp, window, mode='valid') % MOD
	else:
		dp = np.roll(dp[idx], int(s))
print(dp[5] % MOD)


S = input()
modulo = 10 ** 9 + 7
remainder = {0: 1}
for s in S:
	rx = {r: 0 for r in range(13)}
	for n in range(10) if s == '?' else [int(s)]:
		for r in remainder:
			r2 = (r * 10 + n) % 13
			rx[r2] += remainder[r]
			rx[r2] = rx[r2] % modulo
	remainder = rx
print(remainder[5] % modulo)


MOD = 10 ** 9 + 7
S = input()
dp = [0] * 13
dp[0] = 1
for i in range(len(S)):
	cdp = [0] * 13
	tmpS = 0
	if S[i] == '?':
		tmpS = -1
	else:
		tmpS = int(S[i])
	for j in range(10):
		if tmpS != -1 and tmpS != j:
			continue
		for k in range(13):
			cdp[(k * 10 + j) % 13] += dp[k]
			cdp[(k * 10 + j) % 13] %= MOD
	dp = cdp[:]
print(dp[5])


s = input()
dp = [[0 for i in range(13)] for j in range(len(s) + 1)]
mod = 10 ** 9 + 7
dp[0][0] = 1
for i in range(len(s)):
	for j in range(10):
		if s[i] != '?' and int(s[i]) != j:
			continue
		for k in range(13):
			dp[i + 1][(j + 10 * k) % 13] += dp[i][k]
			dp[i + 1][(j + 10 * k) % 13] %= mod
print(dp[-1][5])


S = input()
MOD = 10 ** 9 + 7
N = len(S)
dp = [[0 for _ in range(13)] for _ in range(N + 1)]
dp[0][0] = 1
for i in range(N):
	for j in range(0, 10):
		if S[i] != '?' and S[i] != str(j):
			continue
		for k in range(0, 13):
			dp[i + 1][(k * 10 + j) % 13] += dp[i][k]
	for j in range(0, 13):
		dp[i + 1][j] %= MOD
print(dp[N][5])


mod = 10 ** 9 + 7
r = [[(j - k) * 9 % 13 for j in range(10)] for k in range(13)]
dp = [1] + [0] * 12
for c in input():
	dp = [sum((dp[j] for j in k)) % mod for k in r] if c > '9' else [dp[(int(c) - k) * 9 % 13] for k in range(13)]
print(dp[5])


P = [1, 10, 9, 12, 3, 4]
m = 10 ** 9 + 7

def f(A, p, N):
	if p == 0:
		return [1 & (i in N) for i in range(13)]
	p %= 6
	B = [0] * 13
	for n in N:
		for i in range(13):
			c = (i + n * P[p]) % 13
			B[c] = (B[c] + A[i]) % m
	return B
S = reversed(input())
A = [0]
for (p, s) in enumerate(S):
	if s == '?':
		A = f(A, p, range(10))
	else:
		A = f(A, p, [int(s)])
print(A[5])


s = input()
n = len(s)
dp = [[0 for _ in range(13)] for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
	if s[i] == '?':
		c = -1
	else:
		c = int(s[i])
	for j in range(10):
		if c != -1 and c != j:
			continue
		for ki in range(13):
			dp[i + 1][(ki * 10 + j) % 13] += dp[i][ki]
	for j in range(13):
		dp[i + 1][j] %= 10 ** 9 + 7
print(dp[n][5] % (10 ** 9 + 7))


S = list(input())
L = len(S)
mod = 10 ** 9 + 7
dp = [[0] * 13 for _ in range(2)]
dp[0][0] = 1
(now, next) = (1, 0)
for i in range(L):
	c = S[i]
	(now, next) = (next, now)
	for j in range(13):
		if c == '?':
			for k in range(10):
				dp[next][(j * 10 + k) % 13] += dp[now][j]
		else:
			dp[next][(j * 10 + int(c)) % 13] += dp[now][j]
	for j in range(13):
		dp[next][j] %= mod
		dp[now][j] = 0
print(dp[next][5])


s = input()
frommap = []
for d in range(10):
	frommap.append([0] * 13)
	for m in range(13):
		m2 = (m * 10 + d) % 13
		frommap[d][m2] = m
dp = [1] + [0] * 12
for c in s:
	if c == '?':
		dp = [sum((dp[f] for f in fromlist)) % 1000000007 for fromlist in zip(*frommap)]
	else:
		dp = [dp[f] for f in frommap[int(c)]]
print(dp[5])


import numpy as np
from numpy.fft import rfft, irfft
mod = 10 ** 9 + 7
S = input()
mat = []
for i in range(6):
	w = np.zeros(13)
	for j in range(10):
		w[10 ** i * j % 13] += 1
	mat.append(rfft(w))
ress = [[10 ** i * j % 13 for j in range(10)] for i in range(6)]
state = np.zeros(13)
state[0] = 1
state = rfft(state)
keta = 0
res = 5
for s in reversed(S):
	if s == '?':
		state = state * mat[keta % 6]
	else:
		res -= ress[keta % 6][int(s)]
	if state[0] >= 2 ** 50:
		state = np.round(irfft(state, 13))
		state = rfft(np.remainder(state, mod))
	keta += 1
state = irfft(state, 13)
print(int(np.round(np.real(state[res % 13]))) % mod)


s = input()
dp = [1] + [0] * 12
for c in s:
	newdp = [0] * 13
	for d in range(10) if c == '?' else [int(c)]:
		for m in range(13):
			m2 = (m * 10 + d) % 13
			newdp[m2] = (newdp[m2] + dp[m]) % 1000000007
	dp = newdp
print(dp[5])


def solve():
	S = input()
	mod = 10 ** 9 + 7
	modmap = []
	for i in range(10):
		modmap.append([0] * 13)
		for j in range(13):
			k = (j * 10 + i) % 13
			modmap[i][k] = j
	dp = [1] + [0] * 12
	for s in S:
		if s == '?':
			dp = [sum((dp[l] for l in modlist)) % mod for modlist in zip(*modmap)]
		else:
			modlist = modmap[int(s)]
			dp = [dp[modlist[l]] % mod for l in range(13)]
	print(dp[5])

def __starting_point():
	solve()
__starting_point()


MOD = 10 ** 9 + 7
S = input()
LS = len(S)
dp = [[0] * 13 for _ in range(LS + 1)]
dp[0][0] = 1
for k in range(LS):
	s = S[k]
	if s == '?':
		add = range(10)
	else:
		add = [int(s)]
	for i in range(13):
		for a in add:
			dp[k + 1][(i * 10 + a) % 13] += dp[k][i]
	dp[k + 1] = [x % MOD for x in dp[k + 1]]
print(dp[LS][5])


S = input()
dp = [[0] * 13 for j in range(len(S) + 1)]
mod = 10 ** 9 + 7
dp[0][0] = 1
k = 1
L0 = list(range(10))
for s in S:
	if '?' == s:
		L = L0
	else:
		L = [int(s)]
	for l in L:
		for i in range(13):
			tmp = i * 10 + l
			m = tmp % 13
			dp[k][m] = (dp[k][m] + dp[k - 1][i]) % mod
	k += 1
print(dp[k - 1][5])


S = input()
A = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
a = 10 ** 9 + 7
for i in range(len(S)):
	B = A[:]
	if S[i] == '?':
		A[0] = (B[0] + B[9] + B[5] + B[1] + B[10] + B[6] + B[2] + B[11] + B[7] + B[3]) % a
		A[1] = (B[4] + B[0] + B[9] + B[5] + B[1] + B[10] + B[6] + B[2] + B[11] + B[7]) % a
		A[2] = (B[8] + B[4] + B[0] + B[9] + B[5] + B[1] + B[10] + B[6] + B[2] + B[11]) % a
		A[3] = (B[12] + B[8] + B[4] + B[0] + B[9] + B[5] + B[1] + B[10] + B[6] + B[2]) % a
		A[4] = (B[3] + B[12] + B[8] + B[4] + B[0] + B[9] + B[5] + B[1] + B[10] + B[6]) % a
		A[5] = (B[7] + B[3] + B[12] + B[8] + B[4] + B[0] + B[9] + B[5] + B[1] + B[10]) % a
		A[6] = (B[11] + B[7] + B[3] + B[12] + B[8] + B[4] + B[0] + B[9] + B[5] + B[1]) % a
		A[7] = (B[2] + B[11] + B[7] + B[3] + B[12] + B[8] + B[4] + B[0] + B[9] + B[5]) % a
		A[8] = (B[6] + B[2] + B[11] + B[7] + B[3] + B[12] + B[8] + B[4] + B[0] + B[9]) % a
		A[9] = (B[10] + B[6] + B[2] + B[11] + B[7] + B[3] + B[12] + B[8] + B[4] + B[0]) % a
		A[10] = (B[1] + B[10] + B[6] + B[2] + B[11] + B[7] + B[3] + B[12] + B[8] + B[4]) % a
		A[11] = (B[5] + B[1] + B[10] + B[6] + B[2] + B[11] + B[7] + B[3] + B[12] + B[8]) % a
		A[12] = (B[9] + B[5] + B[1] + B[10] + B[6] + B[2] + B[11] + B[7] + B[3] + B[12]) % a
	else:
		s = int(S[i])
		for i in range(13):
			A[i] = B[(i * 4 + 9 * s) % 13]
print(A[5])


def main():
	S = input().rstrip()
	(ans, MOD) = ([0] * 13, 10 ** 9 + 7)
	ans[0] = 1
	for c in S:
		dp = [0] * 13
		for i in range(13):
			dp[i * 10 % 13] = ans[i] % MOD
		dp += dp
		if c == '?':
			for i in range(13):
				ans[i] = sum(dp[i + 4:i + 14])
		else:
			x = int(c)
			for i in range(13):
				ans[i] = dp[i + 13 - x]
	print(ans[5] % MOD)

def __starting_point():
	main()
__starting_point()


S = input()[::-1]
P = 10 ** 9 + 7
c = 1
X = [1] + [0] * 12
for s in S:
	Y = [0] * 13
	if s == '?':
		for i in range(10):
			for j in range(13):
				Y[(c * i + j) % 13] += X[j]
				Y[(c * i + j) % 13] %= P
	else:
		for j in range(13):
			Y[(c * int(s) + j) % 13] = X[j]
	X = Y
	c = c * 10 % 13
print(X[5])


import numpy as np
s = input()
effects = [1, 10, 9, 12, 3, 4]
mod = 10 ** 9 + 7
amari = np.array([1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
arrays = [np.eye(13, k=i, dtype=np.int64) + np.eye(13, k=i - 13, dtype=np.int64) for i in range(13)]
brrays = [sum((arrays[c * effects[i] % 13] for c in range(10))) for i in range(6)]
for (i, c) in enumerate(reversed(s)):
	if c != '?':
		c = int(c)
		array = arrays[c * effects[i % 6] % 13]
		amari = np.dot(amari, array)
	else:
		array = brrays[i % 6]
		amari = np.dot(amari, array) % mod
print(amari[5])


MOD = int(1000000000.0 + 7)
N = int(100000.0)
M = 13
s = input()
dp = [[0 for x in range(M)] for x in range(N + 10)]
dp[0][0] = 1
for i in range(len(s)):
	for j in range(M):
		for k in range(10):
			if s[i] == '?' or s[i] == str(k):
				dp[i + 1][(j * 10 + k) % M] += dp[i][j]
				dp[i + 1][(j * 10 + k) % M] %= MOD
print(dp[len(s)][5])


S = input()
N = len(S)
su = 0
L = [0] * 13
L[0] = 1
M = [1, 10, 9, 12, 3, 4]
mod = 10 ** 9 + 7
for (i, c) in enumerate(S[::-1]):
	m = M[i % 6]
	if c == '?':
		Lc = L[:]
		for j in range(m, m * 10, m):
			for k in range(13):
				idx = (k + j) % 13
				L[idx] = (L[idx] + Lc[k]) % mod
	else:
		su += int(c) * m
print(L[(-su + 5) % 13])


mod = 10 ** 9 + 7
s = input()
dp = [0] * 13
dp[0] = 1
for i in range(len(s)):
	dp2 = [0] * 13
	for j in range(10):
		if (s[i] == '?') | (s[i] == str(j)):
			for k in range(13):
				dp2[(10 * k + j) % 13] += dp[k]
				dp2[(10 * k + j) % 13] %= mod
	dp = dp2
print(dp[5])


R10 = list(range(10))
R13 = list(range(13))
S = input()
R = [[(M - N) * 4 % 13 for N in R10] for M in R13]
AM = 10 ** 9 + 7
MOD = [1] + [0] * 12
for D in S:
	if D == '?':
		MOD = [sum([MOD[N] for N in M]) % AM for M in R]
	else:
		C = int(D)
		MOD = [MOD[M[C]] for M in R]
print(MOD[5])


s = input()
mod = 10 ** 9 + 7
dp = [1] + [0] * 12
for c in s:
	tmp = dp[:]
	if c == '?':
		dp = [0] * 13
		for n in range(10):
			for i in range(13):
				index = (10 * i + n) % 13
				dp[index] = (dp[index] + tmp[i]) % mod
	else:
		n = int(c)
		for i in range(13):
			dp[(10 * i + n) % 13] = tmp[i]
print(dp[5])


s = input()
n = len(s)
now = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
for i in range(n):
	last = now
	now = [0 for _ in range(13)]
	here = s[i]
	if here == '?':
		for k in range(10):
			for j in range(13):
				now[(10 * j + k) % 13] += last[j]
	else:
		k = int(here)
		for j in range(13):
			now[(10 * j + k) % 13] += last[j]
	for j in range(13):
		now[j] %= 10 ** 9 + 7
print(now[5])


import sys
import numpy as np
from collections import defaultdict

def input():
	return sys.stdin.readline().rstrip()

def convolve(x, y):
	MOD = 10 ** 9 + 7
	z = np.convolve(x, y) % MOD
	z[:12] += z[13:25]
	return z[:13] % MOD

def main():
	mod = 10 ** 9 + 7
	S = input()[::-1]
	dp = np.zeros((len(S), 13), dtype='int64')
	amari = 1
	if S[0] == '?':
		for j in range(10):
			dp[0][j] = 1
	else:
		dp[0][int(S[0])] = 1
	for i in range(1, len(S)):
		arr = np.zeros(13, dtype='int64')
		amari = 10 * amari % 13
		if S[i] == '?':
			for si in range(10):
				arr[amari * si % 13] += 1
		else:
			arr[amari * int(S[i]) % 13] = 1
		dp[i] = convolve(dp[i - 1], arr)
	print(dp[len(S) - 1][5])

def __starting_point():
	main()
__starting_point()


from copy import copy
MOD = 10 ** 9 + 7
s = input()
count = [0 for _ in range(13)]
count[0] = 1
for i in range(len(s)):
	new = [0 for _ in range(13)]
	for m in range(13):
		new[m * 10 % 13] = count[m]
	count = new
	if s[i] != '?':
		div = int(s[i])
		count = count[-div:] + count[:-div]
	else:
		new = [0 for _ in range(13)]
		pre = sum(count[:3])
		SUM = sum(count) % MOD
		for j in range(13):
			pre += count[(j + 3) % 13]
			pre -= count[j % 13]
			new[j] = (SUM - pre) % MOD
		count = new
print(count[5])


s = input()
n = len(s)
mod = 10 ** 9 + 7
dp = [[0] * 13 for i in range(n + 1)]
dp[0][0] = 1
for i in range(n):
	if s[-1 - i] == '?':
		p = [x * pow(10, i, 13) for x in range(0, 10)]
	else:
		p = [int(s[-1 - i]) * pow(10, i, 13)]
	for j in range(13):
		for x in p:
			dp[i + 1][(j + x) % 13] += dp[i][j]
	for j in range(13):
		dp[i + 1][j] %= mod
print(dp[-1][5])


s = input()
pre = [1] + [0] * 12
n = 10 ** 9 + 7
tem = [[i * j % 13 for i in range(10)] for j in range(13)]
t = 1
for i in range(len(s)):
	if s[-1 * i - 1] > '9':
		pre = [sum([pre[k - i] for i in tem[t]]) % n for k in range(13)]
	else:
		te = int(s[-1 * i - 1]) * t % 13
		pre = [pre[i - te] for i in range(13)]
	t = t * 10 % 13
print(pre[5])


MOD = 10 ** 9 + 7

def solve(s, p=13):
	a = [0] * p
	a[0] = 1
	for c in s:
		b = [0] * p
		for i in range(p):
			b[i * 10 % p] = a[i] % MOD
		b += b
		if c == '?':
			for i in range(p):
				a[i] = sum(b[i + 4:i + p + 1])
		else:
			for i in range(p):
				a[i] = b[i + p - int(c)]
	return a[5] % MOD
s = input()
print(solve(s))


M = 10 ** 9 + 7
s = input()
r = range
dp = [[0] * 13, [0] * 13]
dp[0][0] = 1
t = 0
for c in s:
	for i in r(13):
		if c == '?':
			for j in r(10):
				dp[t ^ 1][(i * 10 + j) % 13] += dp[t][i]
		else:
			dp[t ^ 1][(i * 10 + int(c)) % 13] += dp[t][i]
	dp[t] = [0] * 13
	t ^= 1
	for i in r(13):
		dp[t][i] %= M
print(dp[len(s) % 2][5])


s = input()
l = len(s)
mod = pow(10, 9) + 7
dp = [[0 for _ in range(13)] for _ in range(l + 1)]
dp[0][0] = 1
keta = 1
for i in range(1, l + 1):
	num = s[-i]
	if num == '?':
		for j in range(10):
			for k in range(13):
				dp[i][(j * keta + k) % 13] += dp[i - 1][k] % mod
	else:
		num = int(num)
		for k in range(13):
			dp[i][(num * keta + k) % 13] += dp[i - 1][k] % mod
	keta = keta * 10 % 13
print(dp[l][5] % mod)


S = [int(x) if x != '?' else -1 for x in input()]
mod = int(1000000000.0 + 7)
r = [0] * 13
if S[0] != -1:
	r[S[0]] = 1
else:
	for i in range(10):
		r[i] = 1
for i in range(1, len(S)):
	dp = [0] * 26
	for j in range(13):
		dp[j * 10 % 13] += r[j] % mod
	dp[13:26] = dp[0:13]
	r = [0] * 13
	if S[i] == -1:
		s = sum(dp[4:14])
		for j in range(13):
			r[j] += s
			s += dp[j + 1] - dp[4 + j]
	else:
		for j in range(13):
			r[j] += dp[13 - S[i] + j]
print(r[5] % mod)


S = input()
N = len(S)
DP = [0] * 13
DP[0] = 1
A = 0
MOD = 10 ** 9 + 7
T = [1, 10, 9, 12, 3, 4]
A = 0
for i in range(N):
	A *= 10
	if S[i] == '?':
		hoge = [0] * 13
		for j in range(13):
			for k in range(10):
				hoge[(j + k * T[(N - i - 1) % 6]) % 13] = (hoge[(j + k * T[(N - i - 1) % 6]) % 13] + DP[j]) % MOD
		DP = hoge[:]
	else:
		A += int(S[i])
	A = A % 13
print(DP[(5 - A) % 13])


S = input()
N = len(S)
MOD = 10 ** 9 + 7
dp = []
for i in range(N + 1):
	dp.append([0] * 13)
dp[0][0] = 1
for i in range(1, N + 1):
	for j in range(13):
		if S[i - 1] == '?':
			for k in range(10):
				dp[i][(j * 10 + k) % 13] += dp[i - 1][j]
		else:
			dp[i][(j * 10 + int(S[i - 1])) % 13] += dp[i - 1][j]
	for j in range(13):
		dp[i][j] = dp[i][j] % MOD
print(dp[N][5] % MOD)


S = input()
n = len(S)
p = 10 ** 9 + 7
DP = [[0] * 13 for i in range(n + 1)]
DP[0][0] = 1
for i in range(1, n + 1):
	for j in range(13):
		if S[i - 1] == '?':
			DP[i][j] = sum([DP[i - 1][4 * (j - k) % 13] for k in range(10)]) % p
		else:
			k = int(S[i - 1])
			DP[i][j] = DP[i - 1][4 * (j - k) % 13]
print(DP[n][5])


X = [1] + [0] * 12
for s in input():
	X = [sum([X[(i - k) * 9 % 13] for i in (range(10) if s > '9' else [int(s)])]) % (10 ** 9 + 7) for k in range(13)]
print(X[5])


MOD = 1000000007
s = str(input())
n = len(s)
dp = [[0 for i in range(13)] for j in range(n + 1)]
dp[0][0] = 1
for i in range(n):
	c = -1 if s[i] == '?' else int(s[i])
	for j in range(10):
		if c != -1 and c != j:
			continue
		for ki in range(13):
			dp[i + 1][(ki * 10 + j) % 13] += dp[i][ki]
	for j in range(13):
		dp[i + 1][j] %= MOD
print(dp[n][5])


M = 10 ** 9 + 7
s = input()
r = range
k = [1] + [0] * 12
for c in s:
	l = [0] * 13
	for i in r(13):
		if c == '?':
			for j in r(10):
				l[(i * 10 + j) % 13] += k[i]
		else:
			l[(i * 10 + int(c)) % 13] += k[i]
	for i in r(13):
		k[i] = l[i] % M
print(k[5])


MOD = 10 ** 9 + 7
S = input()
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
for (i, s) in enumerate(S):
	pattern = range(10) if s == '?' else [int(s)]
	for p in pattern:
		for j in range(13):
			mod = (j * 10 + p) % 13
			dp[i + 1][mod] += dp[i][j]
			dp[i + 1][mod] %= MOD
print(dp[-1][5])


S = input()
N = len(S)
MOD = 10 ** 9 + 7
dp = [[0] * 13 for i in range(N + 1)]
dp[0][0] = 1
for i in range(N):
	for j in range(13):
		for k in range(10):
			if S[i] == str(k) or S[i] == '?':
				dp[i + 1][(j * 10 + k) % 13] += dp[i][j]
				dp[i + 1][(j * 10 + k) % 13] %= MOD
print(dp[N][5])


s = input()
n = len(s)
dp1 = [0 for _ in range(13)]
dp1[0] = 1
move = [[] for _ in range(13)]
for i in range(10):
	for j in range(13):
		move[(10 * j + i) % 13].append(j)
for i in range(n):
	dp2 = [0 for _ in range(13)]
	if s[i] == '?':
		si = list(range(10))
		for (mod, ex) in enumerate(move):
			dp2[mod] += sum([dp1[x] for x in ex])
	else:
		si = int(s[i])
		for j in range(13):
			dp2[(10 * j + si) % 13] += dp1[j]
	dp1 = [x % (10 ** 9 + 7) for x in dp2]
print(dp1[5])


s = input()
mod = 10 ** 9 + 7
l = len(s)
s = [int(e) if e != '?' else -1 for e in s]
dp = [[0] * 13 for _ in range(l + 1)]
dp[0][0] = 1
for i in range(l):
	for k in range(10):
		if s[i] == -1 or s[i] == k:
			for j in range(13):
				nj = (j * 10 + k) % 13
				dp[i + 1][nj] += dp[i][j]
				dp[i + 1][nj] %= mod
ans = dp[l][5]
print(ans)


def main():
	s = input()
	divisor = 10 ** 9 + 7
	dp = [[0] * 13 for _ in range(len(s) + 1)]
	dp[0][0] = 1
	lut = [i % 13 for i in range(130)]
	list10 = list(range(10))
	list13 = list(range(13))
	for i in range(len(s)):
		dpi = dp[i]
		dpi1 = dp[i + 1]
		if s[i] == '?':
			j10 = 0
			for j in list13:
				dpij = dpi[j]
				for k in list10:
					dpi1[lut[j10 + k]] += dpij
				j10 += 10
		else:
			t = int(s[i])
			for j in list13:
				dpi1[t] += dpi[j]
				t = lut[t + 10]
		for k in list13:
			dpi1[k] %= divisor
	print(dp[len(s)][5])
main()


s = list(input())
s.reverse()
MOD = 10 ** 9 + 7
dp = [[0 for _ in range(13)] for _ in range(len(s) + 1)]
dp[0][0] = 1
for i in range(len(s)):
	nd = s[i]
	p = pow(10, i, 13)
	for mod in range(13):
		dp[i][mod] %= MOD
		for d in range(10):
			if nd != '?' and str(d) != nd:
				continue
			nmod = (d * p + mod) % 13
			dp[i + 1][nmod] += dp[i][mod]
print(dp[-1][5] % MOD)


S = input()
S = S[::-1]
mod = 10 ** 9 + 7
dp = [0] * 13
dp[0] = 1
for i in range(len(S) - 1, -1, -1):
	ch = int(S[i]) if S[i] != '?' else -1
	temp = [0] * 13
	for d in range(10):
		if ch != -1 and ch != d:
			continue
		for m in range(13):
			temp[(10 * m + d) % 13] += dp[m]
	for m in range(13):
		temp[m] %= mod
	dp = temp
print(dp[5])


s = input()
mod = 10 ** 9 + 7
res = [0] * 13
res[0] = 1
for i in s:
	dp = [0] * 13
	for j in range(13):
		dp[j * 10 % 13] = res[j] % mod
	dp += dp
	if i == '?':
		for k in range(13):
			res[k] = sum(dp[k + 4:k + 14])
	else:
		for k in range(13):
			res[k] = dp[k + 13 - int(i)]
print(res[5] % mod)


from sys import stdin
import numpy as np

def main():
	readline = stdin.readline
	mod = 10 ** 9 + 7
	s = readline().strip()
	n = len(s)
	convert = [[0] * 13 for i in range(13)]
	for a in range(13):
		for b in range(10):
			convert[a][(10 * a + b) % 13] = 1
	convert = np.array(convert, dtype=np.int64)
	dp = np.zeros(13, dtype=np.int64)
	dp[0] = 1
	for i in range(n):
		if s[i] == '?':
			tmp = np.dot(dp, convert)
		else:
			x = int(s[i])
			tmp = np.zeros(13, dtype=np.int64)
			for j in range(13):
				tmp[(j * 10 + x) % 13] = dp[j]
		tmp %= mod
		dp = tmp
	print(dp[5])

def __starting_point():
	main()
__starting_point()


d = [0] * 13
d[0] = 1
m = 1
mmod = 1
t = input()[::-1]
mod = 10 ** 9 + 7
zero = [0] * 13
for c in t:
	e = zero[:]
	for i in range(10) if c == '?' else [int(c)]:
		for j in range(13):
			k = (i * m + j) % 13
			e[k] += d[j]
			e[k] %= 1000000007
	d = e
	m = 10 * m % 13
print(d[5])


mod = 10 ** 9 + 7
s = input()
cur = [0] * 13
cur[0] = 1
d = 1
for c in s[::-1]:
	if c != '?':
		l = [int(c)]
	else:
		l = [j for j in range(10)]
	tmp = [0] * 13
	for j in l:
		for k in range(13):
			ind = (j * d + k) % 13
			tmp[ind] += cur[k]
			tmp[ind] %= mod
	cur = tmp
	d *= 10
	d %= 13
print(cur[5])


S = input()
N = len(S)
dp = [[0 for _ in range(13)] for _ in range(N + 1)]
dp[0][0] = 1
mod = 10 ** 9 + 7
for i in range(N):
	for j in range(13):
		if S[i] == '?':
			for d in range(10):
				dp[i + 1][(j * 10 + d) % 13] += dp[i][j] % mod
		else:
			d = int(S[i])
			dp[i + 1][(j * 10 + d) % 13] += dp[i][j] % mod
print(dp[N][5] % mod)


s = input()
n = len(s)
dp = [[0] * 13 for _ in range(n + 1)]
dp[0][0] = 1
mod = 10 ** 9 + 7
for i in range(n):
	c = s[i]
	if c == '?':
		V = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
	else:
		V = [int(c)]
	for v in V:
		d = v * pow(10, n - i - 1, 13) % 13
		for j in range(13):
			dp[i + 1][(j + d) % 13] += dp[i][j]
	for j in range(13):
		dp[i + 1][j % 13] %= mod
print(dp[n][5])


S = input()
memo_ls = [[0 for j in range(13)] for i in range(len(S) + 1)]
memo_ls[0][0] = 1
for i in range(len(S)):
	for _ in range(10):
		if S[i] != '?' and int(S[i]) != _:
			continue
		for j in range(13):
			memo_ls[i + 1][(j * 10 + _) % 13] += memo_ls[i][j]
	for j in range(13):
		memo_ls[i + 1][j] %= 10 ** 9 + 7
print(memo_ls[len(S)][5])


M = 10 ** 9 + 7
text = input()
lst = list(text)
lst.reverse()
digit = len(lst)
six = [[0, 0], [0, 0], [0, 0], [0, 0], [0, 0], [0, 0]]
for i in range(digit):
	if lst[i] == '?':
		six[i % 6][1] = six[i % 6][1] + 1
	else:
		six[i % 6][0] = (six[i % 6][0] + int(lst[i])) % 13
rem = -(six[0][0] - 3 * six[1][0] - 4 * six[2][0] - 1 * six[3][0] + 3 * six[4][0] + 4 * six[5][0] - 5) % 13

def mat1(ls):
	val_ls = [0] * 13
	for i in range(13):
		val_ls[i] = (ls[i] + ls[(i - 1) % 13] + ls[(i - 2) % 13] + ls[(i - 3) % 13] + ls[(i - 4) % 13] + ls[(i - 5) % 13] + ls[(i - 6) % 13] + ls[(i - 7) % 13] + ls[(i - 8) % 13] + ls[(i - 9) % 13]) % M
	return val_ls

def mat10(ls):
	val_ls = [0] * 13
	for i in range(13):
		val_ls[i] = (ls[i] + ls[(i + 3) % 13] + ls[(i + 6) % 13] + ls[(i + 9) % 13] + ls[(i + 12) % 13] + ls[(i + 15) % 13] + ls[(i + 18) % 13] + ls[(i + 21) % 13] + ls[(i + 24) % 13] + ls[(i + 27) % 13]) % M
	return val_ls

def mat100(ls):
	val_ls = [0] * 13
	for i in range(13):
		val_ls[i] = (ls[i] + ls[(i + 4) % 13] + ls[(i + 8) % 13] + ls[(i + 12) % 13] + ls[(i + 16) % 13] + ls[(i + 20) % 13] + ls[(i + 24) % 13] + ls[(i + 28) % 13] + ls[(i + 32) % 13] + ls[(i + 36) % 13]) % M
	return val_ls

def mat1000(ls):
	val_ls = [0] * 13
	for i in range(13):
		val_ls[i] = (ls[i] + ls[(i + 1) % 13] + ls[(i + 2) % 13] + ls[(i + 3) % 13] + ls[(i + 4) % 13] + ls[(i + 5) % 13] + ls[(i + 6) % 13] + ls[(i + 7) % 13] + ls[(i + 8) % 13] + ls[(i + 9) % 13]) % M
	return val_ls

def mat10000(ls):
	val_ls = [0] * 13
	for i in range(13):
		val_ls[i] = (ls[i] + ls[(i - 3) % 13] + ls[(i - 6) % 13] + ls[(i - 9) % 13] + ls[(i - 12) % 13] + ls[(i - 15) % 13] + ls[(i - 18) % 13] + ls[(i - 21) % 13] + ls[(i - 24) % 13] + ls[(i - 27) % 13]) % M
	return val_ls

def mat100000(ls):
	val_ls = [0] * 13
	for i in range(13):
		val_ls[i] = (ls[i] + ls[(i - 4) % 13] + ls[(i - 8) % 13] + ls[(i - 12) % 13] + ls[(i - 16) % 13] + ls[(i - 20) % 13] + ls[(i - 24) % 13] + ls[(i - 28) % 13] + ls[(i - 32) % 13] + ls[(i - 36) % 13]) % M
	return val_ls
modulos = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
for j in range(six[0][1]):
	modulos = mat1(modulos)
for j in range(six[1][1]):
	modulos = mat10(modulos)
for j in range(six[2][1]):
	modulos = mat100(modulos)
for j in range(six[3][1]):
	modulos = mat1000(modulos)
for j in range(six[4][1]):
	modulos = mat10000(modulos)
for j in range(six[5][1]):
	modulos = mat100000(modulos)
print(modulos[rem])


r = range
d = [0] * 13
d[0] = 1
for s in input():
	e = [0] * 13
	for j in r(13):
		for k in ([s], r(10))[s > '9']:
			e[(j * 10 + int(k)) % 13] += d[j]
	d = [e % (10 ** 9 + 7) for e in e]
print(d[5])


S = input()
mod = 10 ** 9 + 7
lst = [[0 for e in range(13)] for f in range(len(S) + 1)]
lst[0][0] = 1
for i in range(len(S)):
	if S[i] == '?':
		for j in range(13):
			for k in range(10):
				lst[i + 1][(j * 10 + k) % 13] += lst[i][j]
				lst[i + 1][(j * 10 + k) % 13] %= mod
	else:
		for j in range(13):
			lst[i + 1][(j * 10 + int(S[i])) % 13] += lst[i][j]
			lst[i + 1][(j * 10 + int(S[i])) % 13] %= mod
print(lst[len(S)][5])


S = input()
K = 13
MOD = 10 ** 9 + 7
dp = [0] * K
dp[0] = 1
for s in S:
	newDp = [0] * K
	if s == '?':
		for i in range(10):
			for j in range(K):
				newDp[(j * 10 + i) % K] += dp[j]
	else:
		i = int(s)
		for j in range(K):
			newDp[(j * 10 + i) % K] += dp[j]
	dp = newDp
	for i in range(K):
		dp[i] %= MOD
print(dp[5])


MOD = 10 ** 9 + 7
S = input()
dp_old = [0] * 13
dp_new = [0] * 13
dp_old[0] = 1
for c in S:
	if c == '?':
		for i in range(10):
			for j in range(13):
				dp_new[(j * 10 + i) % 13] += dp_old[j]
	else:
		for i in range(13):
			dp_new[(i * 10 + int(c)) % 13] += dp_old[i]
	dp_old = [i % MOD for i in dp_new]
	dp_new = [0] * 13
print(dp_old[5])


import numpy as np
MOD = 1000000007
S = input()[::-1]
a = 10 ** np.arange(6) % 13
b = np.tile(np.arange(10), (6, 1))
c = a * b.T % 13
c = c.T
f = np.zeros((6, 13, 13), dtype=np.int64)
for i in range(6):
	f[i, 0, c[i]] = 1
	for j in range(12):
		f[i, j + 1] = np.roll(f[i, j], 1)
prev = np.zeros(13, dtype=np.int64)
prev[0] = 1
digit = 0
for (i, c) in enumerate(S):
	k = i % 6
	if c == '?':
		cur = np.dot(prev, f[k]) % MOD
		(prev, cur) = (cur, prev)
	else:
		digit += a[k] * (ord(c) - ord('0'))
m = (5 - digit) % 13
print(prev[m])


S = input()
N = 10 ** 9 + 7
d = {str(i): [int(i == k) for k in range(10)] for i in range(10)}
d['?'] = [1] * 10
l = d[S[0]] + [0] * 3
for i in range(1, len(S)):
	if S[i] == '?':
		l = [sum([l[(k - j) * 4 % 13] for j in range(10)]) % N for k in range(13)]
	else:
		l = [l[(k - int(S[i])) * 4 % 13] for k in range(13)]
print(l[5])


from itertools import accumulate

def solve():
	MOD = 10 ** 9 + 7
	Ss = input()
	dp = [0] * 13
	dp[0] = 1
	for (d, Sd) in enumerate(Ss):
		dp2 = [0] * 26
		for mod13 in range(13):
			if Sd != '?':
				x = int(Sd)
				mod13n = (10 * mod13 + x) % 13
				dp2[mod13n] += dp[mod13]
				dp2[mod13n + 1] -= dp[mod13]
			else:
				mod13n = (10 * mod13 + 0) % 13
				dp2[mod13n] += dp[mod13]
				dp2[mod13n + 10] -= dp[mod13]
		dp2 = list(accumulate(dp2))
		dp = [(a + b) % MOD for (a, b) in zip(dp2[:13], dp2[13:])]
	print(dp[5])
solve()


s = input()[::-1]
cur = [0] * 13
MOD = 10 ** 9 + 7
c = 1
cur[0] = 1
for i in range(len(s)):
	(pre, cur) = (cur, [0] * 13)
	if s[i] == '?':
		for j in range(10):
			for k in range(13):
				cur[(k + j * c) % 13] += pre[k]
	else:
		i = int(s[i])
		for j in range(13):
			cur[(j + i * c) % 13] += pre[j]
	c = c * 10 % 13
	for i in range(13):
		cur[i] = cur[i] % MOD
print(cur[5])