Problem:
 Score : 400 points    Problem Statement 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 1 ??2??5      Sample Output 1 768  For example, 482305, 002865, and 972665 satisfy the condition.       Sample Input 2 ?44      Sample Output 2 1  Only 044 satisfies the condition.       Sample Input 3 7?4      Sample Output 3 0  We may not be able to produce an integer satisfying the condition.       Sample Input 4 ?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76???      Sample Output 4 153716888

Solution (Python):
p = 10 ** 9 + 7
def main():
    s = input()[::-1]
    mod = 13
    dp = [[0] * 13 for _ in range(len(s) + 1)]
    dp[0][0] = 1

    for i in range(len(s)):
        if s[i] == "?":
            for j in range(10):
                d = j * pow(10, i, mod)
                for k in range(13):
                    dp[i + 1][(k + d) % mod] += dp[i][k]
                    dp[i + 1][(k + d) % mod] %= p
        else:
            d = int(s[i]) * pow(10, i, mod)
            for k in range(13):
                dp[i + 1][(k + d) % mod] += dp[i][k]
    print(dp[-1][5])
if __name__ == '__main__':
    main()

Solution (Python):
s = input()[::-1]
mod = 13
p = 10 ** 9 + 7
dp = [[0] * 13 for _ in range(len(s) + 1)]
dp[0][0] = 1

for i in range(len(s)):
    if s[i] == "?":
        for j in range(10):
            d = j * pow(10, i, mod)
            for k in range(13):
                dp[i + 1][(k + d) % mod] += dp[i][k]
                dp[i + 1][(k + d) % mod] %= p
    else:
        d = int(s[i]) * pow(10, i, mod)
        for k in range(13):
            dp[i + 1][(k + d) % mod] += dp[i][k]
print(dp[-1][5])

Solution (Python):
s=list(input())
mod=10**9+7
n=len(s)
for i in range(n):
    if s[i]!="?":
        s[i]=int(s[i])
dp=[[0]*13 for i in range(n+1)]
dp[0][0]=1
for i in range(n):
    if s[i]=="?":
        for k in range(10):
            for j in range(13):
                p=(k+10*j)%13
                dp[i+1][p]+=dp[i][j]
                dp[i+1][p]%=mod

    else:
        for j in range(13):
            p=(s[i]+10*j)%13
            dp[i+1][p]+=dp[i][j]
            dp[i+1][p]%=mod
print(dp[n][5])

Solution (Python):
from collections import defaultdict
s = input()[::-1]
mod = 13
p = 10 ** 9 + 7
dic = defaultdict(int)
dic[0] = 1

for i in range(len(s)):
    tmp = defaultdict(int)
    if s[i] == "?":
        for j in range(10):
            d = j * pow(10, i, mod)
            for k, v in dic.items():
                tmp[(k + d) % mod] += v
                tmp[(k + d) % mod] %= p
    else:
        d = int(s[i]) * pow(10, i, mod)
        for k, v in dic.items():
            tmp[(k + d) % mod] = v
    dic = tmp
print(dic[5] % p)

Solution (Python):
from collections import defaultdict
s = input()
lens = len(s)
"""
1, 10, 100～900に対して13で割って5余るものは存在する？
"""
modl = [[] for i in range(len(s))]
modl[0] = [i for i in range(10)]
for i in range(1, len(s)):
	modl[i] = [(modl[i-1][j]*10)%13 for j in range(10)]
mod = 10**9+7

unta = defaultdict(lambda: 0)
unta[0] += 1
for i, j in enumerate(s[::-1]):
	newunta = defaultdict(lambda: 0)
	if j != "?":
		a = modl[i][int(j)]
		for k in range(13):
			newunta[(k+a)%13] = (newunta[(k+a)%13] + unta[k]) % mod
	else:
		for l in range(10):
			a = modl[i][l]
			for k in range(13):
				newunta[(k+a)%13] = (newunta[(k+a)%13] + unta[k]) % mod
	unta = newunta

print(unta[5] % mod)

Solution (Python):
import collections
s = list(raw_input())
r = 0
mod = 10 ** 9 + 7
h= collections.Counter()
h[0] += 1
for v in s:

	v = int(v) if v != '?' else v
	hh = collections.Counter()
	for u in range(13):
		if v != '?':
			hh[(u * 10 + v) % 13] += h[u]

		else:
			for vv in range(10):
				hh[(u * 10 + vv) % 13] += h[u]
	for k in hh:
		hh[k] %= mod
	h = hh
print h[5]

Solution (Python):
from sys import stdin, setrecursionlimit


def main():
    mod = 10 ** 9 + 7
    input = stdin.buffer.readline
    s = list(input()[:-1].decode())
    n = len(s)

    dp = [0] * 13
    if s[0] == '?':
        for i in range(10):
            dp[i % 13] += 1
    else:
        dp[int(s[0]) % 13] += 1

    for i in range(1, n):
        tmp_dp = [0] * 13
        if s[i] == '?':
            for j in range(13):
                for k in range(10):
                    index = (10 * j + k) % 13
                    tmp_dp[index] += dp[j]
                    tmp_dp[index] %= mod
        else:
            for j in range(13):
                index = (10 * j + int(s[i])) % 13
                tmp_dp[index] += dp[j]
                tmp_dp[index] %= mod
        dp = tmp_dp

    print(dp[5] % mod)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Solution (Python):
s = input()[::-1]

dp = [0] * 13
dp[0] = 1
mod = 10 ** 9 + 7

for i, char in enumerate(s):
    dp_new = [0] * 13

    if char != '?':
        l = [int(char)]
    else:
        l = list(range(10))

    for k in l:
        tmp = pow(10, i, 13)
        tmp = (k * tmp) % 13

        for j in range(13):
            dp_new[(j + tmp) % 13] += dp[j]

    dp = []
    for x in dp_new:
        dp.append(x % mod)

print(dp[5])

Solution (Python):
def main():
    s = input()
    mod = 10 ** 9 + 7

    DP = [[0] * 13 for i in range(len(s) + 1)]
    DP[0][0] = 1
    for ci, c in enumerate(s):
        if c == '?':
            for r in range(13):
                for k in range(10):
                    DP[ci + 1][(r * 10 + k) % 13] += DP[ci][r]
                    DP[ci + 1][(r * 10 + k) % 13] %= mod

        else:
            for r in range(13):
                DP[ci + 1][(r * 10 + int(c)) % 13] += DP[ci][r]
                DP[ci + 1][(r * 10 + int(c)) % 13] %= mod

    print(DP[len(s)][5])


if __name__ == '__main__':
    main()

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

Solution (Python):
def main():
  s=list(input())
  n=len(s)
  dp=[0]*13
  mod=pow(10,9)+7
  if s[-1]=='?':
    dp=[1]*10+[0]*3
  else:
    dp[int(s[-1])]=1
  p_dp=[0]*13
  for i in range(2,n+1):
    if s[-i]=='?':
      for j in range(10):
        a=(j*pow(10,i-1,13))%13
        for k in range(13):
          p_dp[(a+k)%13]+=dp[k]
    else:
      j=int(s[-i])
      a=(j*pow(10,i-1,13))%13
      for k in range(13):
        p_dp[(a+k)%13]+=dp[k]
    
    for k in range(13):
      p_dp[k]%=mod
    dp=[k for k in p_dp]
    p_dp=[0]*13
  print(dp[5])

if __name__=='__main__':
  
  
  main()

Solution (Python):
s=input()
n=len(s)
dp=[[0]*(13) for _ in range(n)]
mod=10**9+7

for i in range(n):
    if i==0:
        if s[i]=='?':
            for j in range(10):
                dp[i][j]=1
        else:
            x=int(s[i])
            dp[i][x]=1
    else:
        if s[i]=='?':
            for k in range(10):
                for j in range(13):
                    dp[i][(j*10+k)%13]+=dp[i-1][j]
                    dp[i][(j*10+k)%13]%=mod
        else:
            x=int(s[i])
            for j in range(13):
                dp[i][(j*10+x)%13]+=dp[i-1][j]
                dp[i][(j*10+x)%13]%=mod
print(dp[n-1][5]%mod)

Solution (Python):
s = input()
len_s = len(s)
mod = 10 ** 9 + 7
dp = [[0] * 13 for i in range(len_s)]
if s[-1] == '?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(s[-1])] = 1

digits = 1
for i in range(1, len_s):
    digits = (digits * 10)%13
    for j in range(13):

        if dp[i - 1][j] > 0:
            if s[-(i + 1)] != '?':
                add = int(s[-(i + 1)]) * digits
                dp[i][(j + add)%13] = (dp[i][(j + add)%13] + dp[i - 1][j])%mod
            else:
                for k in range(10):
                    
                    add = k * digits
                    dp[i][(j + add) % 13] = (dp[i][(j + add) % 13] + dp[i - 1][j]) % mod

print(dp[-1][5] % mod)

Solution (Python):
s = input()
s = s[::-1]
n = len(s)
mod = 10**9 + 7

dp = [[0 for j in range(13)] for i in range(n)]
if s[0] == '?':
    for i in range(10):
        dp[0][i] = 1
else:
    num = int(s[0])
    dp[0][num] = 1

mul = 1
for i in range(1, n):
    mul = (mul*10) % 13
    if s[i] == '?':
        for m in range(10):
            num = (m * mul) % 13
            for j in range(13):
                dp[i][(j+num)%13] = (dp[i][(j+num)%13] + dp[i-1][j]) % mod
    else:
        num = (int(s[i]) * mul) % 13
        for j in range(13):
            dp[i][(j+num)%13] = (dp[i][(j+num)%13] + dp[i-1][j]) % mod

print(dp[n-1][5])

Solution (Python):
S = list(input())
S = S[::-1]
dp = [[0]*13 for _ in range(len(S)+1)]
dp[0][0] = 1
mod = 10**9+7
mul = 1
for i in range(len(S)):
  if S[i] == '?':
    for j in range(10):
      for k in range(13):
        dp[i+1][(j*mul+k)%13] += dp[i][k] % mod
  else:
    s = int(S[i])
    for k in range(13):
      dp[i+1][(s*mul+k)%13] += dp[i][k] % mod

  mul = (mul * 10) % 13
    
print(dp[len(S)][5]%mod)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    s=input()
    len_s=len(s)
    mod=10**9+7
    dp=[[0]*13 for _ in range(len_s+1)] 
    dp[0][0]=1
    for i in range(len_s):
        if s[i]=="?":
            for j in range(13):
                for k in range(10):
                    dp[i+1][(10*j+k)%13]+=dp[i][j]%mod
        else:
            c=int(s[i])
            for j in range(13):
                dp[i+1][(10*j+c)%13]=dp[i][j]
        for j in range(13):
            dp[i+1][j]%=mod
    print(dp[len_s][5])

if __name__=='__main__':
    main()

Solution (Python):
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)


if __name__ == '__main__':
    main()

Solution (Python):
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])

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

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

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

Solution (Python):
s=input()
n=len(s)
mod=10**9+7
dp=[[0]*13 for _ in range(n+1)]
dp[0][0]=1
mul=1

for i in range(n):
    x=s[-(i+1)]  
    if x=='?':
        for k in range(10):
            for j in range(13):
                dp[i+1][(mul*k+j)%13]+=dp[i][j]
                dp[i+1][(mul*k+j)%13]%=mod
    else:
        k=int(x)
        for j in range(13):
            dp[i+1][(mul*k+j)%13]+=dp[i][j]
            dp[i+1][(mul*k+j)%13]%=mod
    mul=mul*10%13

print(dp[n][5])

Solution (Python):
s=input()
n=len(s)
mod=10**9+7
dp=[[0]*13 for _ in range(n+1)]
dp[0][0]=1
mul=1

for i in range(n):
    x=s[-(i+1)]  
    if x=='?':
        for k in range(10):
            for j in range(13):
                dp[i+1][(mul*k+j)%13]+=dp[i][j]
                dp[i+1][(mul*k+j)%13]%=mod
    else:
        k=int(x)
        for j in range(13):
            dp[i+1][(mul*k+j)%13]+=dp[i][j]
            dp[i+1][(mul*k+j)%13]%=mod
    mul=mul*10%13

print(dp[n][5])

Solution (Python):
S = input()[::-1]
N = len(S)
mod = 10**9 + 7
DP = [[0] * 13 for _ in range(N+1)]
DP[0][0] = 1

for i, s in enumerate(S):
    if s != '?':
        a = int(s) * pow(10, i, 13) % 13
        for j in range(13):
            DP[i+1][j] += DP[i][(j-a) % 13] % mod

    else:
        for k in range(10):
            a = k * pow(10, i, 13) % 13
            for j in range(13):
                DP[i + 1][j] += DP[i][(j - a) % 13] % mod

print(DP[N][5] % mod)

Solution (Python):
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])

Solution (Python):
s = input()
n = len(s)
mod = 1000000007
dp = [[0 for i in range(13)] for j in range(n+1)]
dp[0][0] = 1
s = s[::-1]
dec = 1
for i in range(n):
    x = s[i]
    dec %= 13
    if x != '?':
        x = int(x)
        r = (dec * x) % 13
        for j in range(13):
            dp[i+1][j] = dp[i][(j-r)%13]
    else:
        for j in range(10):
            r = (dec * j) % 13
            for k in range(13):
                dp[i+1][k] += dp[i][(k-r)%13] % mod
    dec *= 10
print(dp[-1][5] % mod)

Solution (Python):

import sys
input = sys.stdin.readline









S = input().rstrip()
mod = 10**9+7


dp = [[0 for _ in range(13)] for _ in range(len(S))]


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)):
    if S[i] == "?":
        for j in range(13):
            for k in range(10):
                dp[i][(j*10 + k) % 13] += dp[i-1][j]
                dp[i][(j*10 + k) % 13] %= mod
    else:
        for j in range(13):
            dp[i][(j*10 + int(S[i])) % 13] += dp[i-1][j]
            dp[i][(j*10 + int(S[i])) % 13] %= mod

print(dp[-1][5])

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import fractions
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

S = input()
N = len(S)
modlist = [0] * 13
splitmod = []

if S[0] == "?":
    for i in range(10):
        modlist[i % 13] += 1
else:
    modlist[int(S[0])] += 1
S = S[1:]









for st in S:
    modalta = [0] * 13
    if st == "?":
        
        
        for i in range(10):
            
            for j in range(13):
                opt = (j * 10 + i) % 13
                modalta[opt] += modlist[j]
    else:
        for j in range(13):
            opt = (j * 10 + int(st)) % 13
            modalta[opt] += modlist[j]
    
    for i in range(13):
        modalta[i] %= mod
    modlist = copy.deepcopy(modalta)

print(modlist[5] % mod)

Solution (Python):
mod = 10**9 + 7
S = input()

dp = [[0]*13 for _ in range(len(S)+1)]
dp[0][0] = 1

for i in range(len(S)):
    if S[i] != '?':
        for m in range(13):
            dp[i+1][(10*m+int(S[i])) % 13] += dp[i][m]
            dp[i+1][(10*m+int(S[i])) % 13] %= mod
    else:
        for c in range(10):
            for m in range(13):
                dp[i+1][(10*m+c) % 13] += dp[i][m]
                dp[i+1][(10*m+c) % 13] %= mod

print(dp[len(S)][5])

Solution (Python):
S = input()[::-1]
keta = len(S)
mod = 10 ** 9 + 7

dp = [[0 for _ in range(13)] for _ in range(keta + 1)]
dp[0][0] = 1
tmp = 1
for i in range(1, keta + 1):
    if S[i - 1] != "?":
        x = int(S[i - 1]) * (tmp) % 13
        for j in range(13):
            dp[i][(x + j) % 13] += dp[i - 1][j] % mod
    else:
        for k in range(10):
            x = k * (tmp) % 13
            for j in range(13):
                dp[i][(x + j) % 13] += dp[i - 1][j] % mod
    tmp *= 10
    tmp %= 13

print(dp[keta][5] % mod)

Solution (Python):
s = input().rstrip()

n = [0] * 13
for i in range(13):
    n[i] = (i * 10) % 13

rev = [0] * 13
for i, ni in enumerate(n):
    rev[ni] = i

dp = [[0] * 13 for _ in range(len(s))]

if s[0] == '?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(s[0])] = 1

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

print(dp[-1][5])

Solution (Python):
MOD = 10**9 + 7
s = input()
now = [0] * 13
now[0] = 1
k = 1
for c in reversed(s):
    nxt = [0] * 13
    if c == '?':
        for i in range(10):
            a = k * i % 13
            for j in range(13):
                nxt[(j + a) % 13] += now[j]
                nxt[(j + a) % 13] %= MOD
    else:
        i = int(c)
        a = k * i % 13
        for j in range(13):
            nxt[(j + a) % 13] += now[j]
            nxt[(j + a) % 13] %= MOD
    now = nxt
    k = k * 10 % 13
print(now[5])

Solution (Python):
INF = 10 ** 9 + 7

S = input()

dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  

print(dp[len(S)][5])

Solution (Python):
s = input()
keta = len(s)
mod = 10 ** 9 + 7
dp = [[0] * (13) for _ in range(keta + 1)]
dp[0][0] = 1
for i in range(keta):
    if s[i] == "?":
        num = -1
    else:
        num = int(s[i])
    ni = i + 1
    juu = pow(10, keta - 1 - i, 13)
    for j in range(13):
        nj = j
        if num == -1:
            for d in range(10):
                nj = j + d * juu
                nj %= 13
                dp[ni][nj] += dp[i][j]
                dp[ni][nj] %= mod
                continue
        else:
            nj = j + num * juu
            nj %= 13
            dp[ni][nj] += dp[i][j]
            dp[ni][nj] %= mod
print(dp[keta][5])

Solution (Python):
s = input()

dp = [[0 for i in range(13)] for j in range(len(s)+1)]
dp[0][0]=1
keta = 1
di=10**9+7
ii = len(s)
for i in range(len(s)):
    if s[ii-1-i] != "?":
        for j in range(13):
            dp[i+1][(keta*int(s[ii-1-i])+j)%13]=(dp[i+1][(keta*int(s[ii-1-i])+j)%13]+dp[i][j])%di
    else:
        for j in range(13):
            for num in range(10):
                
                dp[i+1][(keta*num+j)%13]=(dp[i+1][(keta*num+j)%13]+dp[i][j])%di
    keta = (keta*10)%13


print(dp[len(s)][5])

Solution (Python):
S = input()
N = len(S)
MOD = 10**9+7
dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1

base = 1
for i in range(N):
    if S[N-1-i] != '?':
        mi = int(S[N-1-i])*base
        mi %= 13
        for j in range(13):
            dp[i+1][(j+mi)%13] += dp[i][j]
            dp[i+1][(j+mi)%13] %= MOD
    else:
        for j in range(13):
            for k in range(10):
                Ti = base * k
                Ti %= 13
                dp[i+1][(j+Ti)%13] += dp[i][j]
                dp[i+1][(j+Ti)%13] %= MOD
    base *= 10
    base %= 13
print(dp[N][5])

Solution (Python):




def solve():
    S = input()
    mod = 10 ** 9 + 7

    '''
    桁数毎・余りの数字ごとのdpを作成するにあたり、mapを作る.
    たとえば新しい数字Yは前の数字Xの右側に新たに桁を作って
        Y = X(前の数字) * 10 + i(0 <= i <= 9)
    と表せる.
    この Y の余りは、
        Y % 13 = ((X % 13) * 10 + i) % 13
    と表せるので、10 * 13 のマップであらかじめ計算しておくことができる.
    このマップを以下で作っている.
        modmap[新しい桁の数字i][新しい余り(Y % 13 = k)] = 前の数字の時の余り(X % 13 = j)
    '''
    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])


if __name__ == '__main__':
    solve()

Solution (Python):
S = input()
INF = 10 ** 9 + 7

dp = [[0 for _ in range(13)] for _ in range(len(S) + 1)]
index = 1
dp[0][0] = 1
for i in range(len(S)):
    c = S[-i - 1]
    if c == '?':
        for j in range(10):
            for k in range(13):
                dp[i + 1][(j * index + k) % 13] += dp[i][k]
                dp[i + 1][(j * index + k) % 13] %= INF
    else:
        c = int(c)
        for k in range(13):
            dp[i + 1][(c * index + k) % 13] += dp[i][k]
            dp[i + 1][(c * index + k) % 13] %= INF
    index *= 10
    index %= 13

print(dp[len(S)][5])

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

Solution (Python):
s=input()




dp=[[0 for _ in range(13)] for _ in range(len(s))]

MOD=10**9+7

if s[0]!="?":
    dp[0][int(s[0])]=1
else:
    for i in range(10):
        dp[0][i]=1


for i in range(1,len(s)):
    si=s[i]


    if s[i]!="?":
        
        for j in range(13):
            dp[i][(j*10+int(si))%13]+=dp[i-1][j]%MOD
    else:
        for l in range(10):
            for j in range(13):
                dp[i][(j*10+l)%13]+=dp[i-1][j]%MOD
    



print(dp[len(s)-1][5]%MOD)

Solution (Python):



S = input()
n = len(S)

MOD = 10 ** 9 + 7


dp = [[0] * 13 for _ in range(n + 1)]
dp[0][0] = 1

for i, s in enumerate(S):
  for j in range(10):
    if s == "?" or int(s) == j:
      for k in range(13):
        dp[i + 1][(k * 10 + j) % 13] += dp[i][k]
  for k in range(13):
    dp[i + 1][k] %= MOD

print(dp[n][5])

Solution (Python):
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

S = input()

dp = [[0] * 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)):
    if S[i] == '?':
        for j in range(13):
            for k in range(10):
                dp[i][(j * 10 + k) % 13] += dp[i-1][j]
                dp[i][(j + 10 + k) % 13] %= mod
    else:
        for j in range(13):
            dp[i][(j * 10 + int(S[i])) % 13] += dp[i-1][j]
            dp[i][(j * 10 + int(S[i])) % 13] %= mod
print(dp[len(S) - 1][5])

Solution (Python):
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
geta = lambda fn: map(fn, readline().split())
gete = lambda fn: fn(input())




def main():
    S = gete(str)[::-1]
    m, mod = 13, 10**9 + 7
    prev, curr = [0] * m, [0] * m
    base = []

    s0, b = 0, 1
    for i, c in enumerate(S):
        if c == "?":
            base.append(b)
        else:
            s0 = (s0 + b * int(c)) % m
        b = (b * 10) % m
    curr[s0] = 1

    for b in base:
        prev, curr = curr, [0] * m

        for d in range(10):
            ad = d * b
            for r, p in enumerate(prev):
                curr[(r + ad) % m] += p

            for r, c in enumerate(curr):
                curr[r] = c % mod

    print(curr[5])


if __name__ == "__main__":
    main()

Solution (Python):
S = input()
N = len(S)

MOD = 10**9 + 7
dp = [[0 for _ in range(13)] for _ in range(N)]  


if S[0] == "?":
    for j in range(10):
        dp[0][j] = 1
else:
    dp[0][int(S[0])] = 1


for i in range(1, N):
    if S[i] == "?":
        for si in range(10):
            for j in range(13):
                dp[i][(j*10 + si)%13] += dp[i-1][j]
                dp[i][(j*10 + si)%13] %= MOD
    else:
        si = int(S[i])
        for j in range(13):
            dp[i][(j*10 + si)%13] += dp[i-1][j]
            dp[i][(j*10 + si)%13] %= MOD

print(dp[N-1][5])

Solution (Python):
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
geta = lambda fn: map(fn, readline().split())
gete = lambda fn: fn(input())




def main():
    S=gete(str)[::-1]
    m=13
    mod=10**9 + 7
    prev, curr=[0]*m, [0]*m
    base,  wild=[], []

    s0, b=0, 1
    for i, c in enumerate(S):
        base.append(b)
        if c == "?":
            wild.append(i)
        else:
            s0=(s0 + b * int(c)) % m
        b=(b * 10) % m

    curr[s0]=1

    for wi in wild:
        prev, curr=curr, [0]*m

        for d in range(10):
            ad=d*base[wi]
            for r, p in enumerate(prev):
                curr[(r + ad) % m] += p

            for r, c in enumerate(curr):
                curr[r]=c % mod

    print(curr[5])


if __name__ == "__main__":
    main()

Solution (Python):
S = input()
N = len(S)

MOD = 10**9 + 7
dp = [[0 for _ in range(13)] for _ in range(N)]  


if S[0] == "?":
    for j in range(10):
        dp[0][j] = 1
else:
    dp[0][int(S[0])] = 1



for i in range(1, N):
    si = S[i]
    if si == "?":
        for si_cand in range(10):
            for j in range(13):
                dp[i][(j*10+si_cand)%13] += dp[i-1][j] % MOD
    else:
        for j in range(13):
            dp[i][(j*10+int(si))%13] += dp[i-1][j] % MOD

print(dp[N-1][5] % MOD)

Solution (Python):
M = (10**9+7)
s = list(input())[::-1]

mo = []
fixed = 0
for i in range(len(s)):
  if s[i]!='?':
    t = int(s[i])
    fixed += (t*pow(10,i,13))
    fixed %= 13
  else:
    t = []
    for j in range(10):
      t.append((j*pow(10,i,13)%13))
    mo.append(tuple(t))

if len(mo)==0:
  if fixed == 5:
    print(1)
  else:
    print(0)
  exit()
  
dp = [[-1]*13 for _ in range(len(mo))]

for m in mo[0]:
  dp[0][m] = 1
for i in range(len(mo)-1):
  for j in range(13):
    if dp[i][j]==-1:
      continue
    dp_i = dp[i+1]
    dp_j = dp[i]
    for m in mo[i+1]:
      p = (j+m)%13
      if dp_i[p] == -1:
        dp_i[p] = 0
      dp_i[p] += dp_j[j]
      dp_i[p]  %= M

ans = dp[-1][(18-fixed)%13] % M 
if dp[-1][(18-fixed)%13] == -1:
  print(0)
  exit()
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
mod = 10**9 + 7

s = input().rstrip()
n = len(s)
s = s[::-1]

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

Solution (Python):
import sys
input = sys.stdin.readline

S = list(input()[:-1])
S.reverse()
dp = [[0]*13 for _ in range(len(S)+1)]
dp[0][0] = 1
MOD = 10**9+7

for i in range(len(S)):
    p = pow(10, i, 13)
    
    if S[i]=='?':
        for j in range(10):
            for k in range(13):
                dp[i+1][(k+j*p)%13] += dp[i][k]
                dp[i+1][(k+j*p)%13] %= MOD
    else:
        for j in range(13):
            dp[i+1][(j+int(S[i])*p)%13] += dp[i][j]
            dp[i+1][(j+int(S[i])*p)%13] %= MOD

print(dp[len(S)][5])

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

Solution (Python):
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 i in range(M):
                newDp[(i * 10 + s) % M] += dp[i]
    else:
        s = int(s)
        for i in range(M):
            newDp[(i * 10 + s) % M] = dp[i]
    for i in range(M):
        dp[i] = newDp[i] % MOD

print(dp[5])

Solution (Python):
s=input()
lim=10**9+7
dp = [[0 for _ in range(13)] for _ in range(len(s))]
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)):
    for j in range(13):
        if s[i] ==  "?":
            for k in range(10):
                dp[i][(j*10 + k)%13] = (dp[i][(j*10 + k)%13]+dp[i-1][j])%lim
        else:
            dp[i][(j*10 + int(s[i]))%13] = (dp[i][(j*10 + int(s[i]))%13]+dp[i-1][j])%lim
print(dp[-1][5])

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

Solution (Python):





S = input()
N = len(S)
MOD = 10**9 + 7


dp = [[0 for _ in range(13)] for _ in range(N+1)]
dp[0][0] = 1

"""
遷移
dp[i][j] -> dp[i+1][j+m] : i-1まで見た時あまりがkになる数字について、末尾にS[i]が追加されると、i-1までのあまりは10倍になるから、10*j+mを13で割ったあまりが新たなあまり
: S[i]が？の場合可能
dp[i][j] -> dp[i+1][k]   : S[i]もS[i-1]も？ではない

"""

for i in range(N):
    for j in range(13):
        if S[i] == "?":
            
            for num in range(10):
                dp[i+1][(10*j + num) % 13] += dp[i][j]
                dp[i+1][(10*j + num) % 13] %= MOD
        else:
            
            dp[i+1][(10*j + int(S[i])) % 13] += dp[i][j]
            dp[i+1][(10*j + int(S[i])) % 13] %= MOD


print(dp[-1][5])