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):
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok


def main():
    S = input()
    d = 1
    dp = [0] * 13
    dp[0] = 1
    dp_n = [None] * 13
    for s in reversed(S):
        for i in range(13):
            dp[i] %= N1097
            dp_n[i] = 0
        if s == '?':
            for s in range(10):
                diff = (s*d) % 13
                for i in range(13):
                    dp_n[(i+diff)%13] += dp[i]
        else:
            s = int(s)
            diff = (s*d) % 13
            for i in range(13):
                dp_n[(i+diff)%13] += dp[i]
        dp_n, dp = dp, dp_n
        d = (10 * d) % 13
    print(dp[5] % N1097)

main()

Solution (Python):
MOD1 = 13
MOD2 = 10 ** 9 + 7

S = input()
N = len(S)
dp = [[0 for _ in range(MOD1)] for _ in range(N)]

if S[0] == '?':
    for k in range(10):
        dp[0][k % MOD1] += 1
else:
    dp[0][int(S[0]) % MOD1] += 1

for i in range(N-1):
    if S[i+1] == '?':
        for j in range(MOD1):
            for k in range(10):
                tmp_j = (j * 10 + k) % MOD1
                dp[i+1][tmp_j] += dp[i][j]
                dp[i + 1][tmp_j] %= MOD2
    else:
        for j in range(MOD1):
            tmp_j = (j * 10 + int(S[i+1])) % MOD1
            dp[i+1][tmp_j] += dp[i][j]
            dp[i + 1][tmp_j] %= MOD2

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

Solution (Python):
MOD = int(1e9+7)
def add(x, y):
    return ((x%MOD + MOD) % MOD + (y%MOD + MOD) % MOD) % MOD

s = input()
dp = [[0] * 13 for _ in range(len(s)+1)]
dp[0][0] = 1 
mul = 1
for i in range(len(s)):
    if s[-(i+1)] == "?":
        for k in range(10):
            for j in range(13):
                idx = (mul*k + j)%13
                dp[i+1][idx] = add(dp[i+1][idx], dp[i][j])
    else:
        k = int(s[-(i+1)])
        for j in range(13):
            idx = (mul*k + j)%13
            dp[i+1][idx] = add(dp[i+1][idx], dp[i][j])
    mul = mul * 10 % 13 
print(dp[len(s)][5])

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

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:
  k = int(S[0])
  dp[0][k] = 1

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

print(dp[-1][5])

Solution (Python):
p = 10**9 + 7
S = input()
N = len(S)

dp = [[0 for _ in range(13)] for _ in range(2)]
dp[0][0] = 1 
r = 0

for i in range(N - 1,  -1,  -1):  
    w = 1 if i == N - 1 else (w * 10) % 13 
    r = 1 - r  
    if S[i] == '?':
        for j in range(13):
            for k in range(10): 
                dp[r][(j + w * k) % 13] += dp[1 - r][j]
                if dp[r][(j + w * k) % 13] >= p:
                    dp[r][(j + w * k) % 13] -= p
    else:
        k = int(S[i])
        for j in range(13):
            dp[r][(j + w * k) % 13] = dp[1 - r][j]

    dp[1 - r] = [0] * 13

print(dp[r][5])

Solution (Python):
s=input()
dp=[[0]*13 for _ in range(len(s))]
if s[0]=='?':
  dp[0]=[1]*10+[0]*3
else:
  dp[0][int(s[0])]+=1

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

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input():
    return sys.stdin.readline().rstrip()

def main():
    S=list(input())
    N=len(S)
    dp=[[0]*13 for _ in range(10**5*2)]
    dp[0][0]=1
    for i,s in enumerate(S):
        if s=='?':
            for k in range(10):
                for j in range(13):
                    dp[i+1][(j*10+k)%13]+=dp[i][j]
                    dp[i+1][(j*10+k)%13]%=MOD
        else:
            for j in range(13):
                dp[i+1][(j*10+int(s))%13]+=dp[i][j]
                dp[i+1][(j*10+int(s))%13]%=MOD
    print(dp[N][5])

if __name__ == '__main__':
    main()

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


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

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

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

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


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

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

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

Solution (Python):

S = input()
N = len(S)
mod=13
mod2=10**9+7
def pow_mod(x,n):
    if n==0:
        return 1
    
    K = 1
    while n>1:
        if n%2 != 0:
            K *= x
            K %= mod
        x *= x
        x %= mod
        n //= 2

    return (K*x)%mod


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

for i in range(1,N):
    amari = pow_mod(10,i)
    if S[i]=="?":
        for j in range(13):
            for k in range(10):
                dp[i+1][j] += dp[i][(j-amari*k)%mod]
            dp[i+1][j] %= mod2
    else:
        for j in range(13):
            dp[i+1][j] += dp[i][(j-amari*int(S[i]))%mod]
            dp[i+1][j] %= mod2

print(dp[N][5])

Solution (Python):
S = input()
memo = [[0]*(13) for _ in range(len(S))]
mod = 10**9 + 7
def main():
    cnt = 1
    R = []
    for _ in range(len(S)):
        R.append(cnt)
        cnt = (cnt*10)%13
    dic = [{} for _ in range(13)]
    for i in range(13):
        for j in range(10):
            if (i*j)%13 not in dic[i]:
                dic[i][(i*j)%13] = 1
            else:
                dic[i][(i*j)%13] += 1
    if S[-1] == "?":
        for i in range(10):
            memo[0][i] = 1
    else:
        memo[0][int(S[-1])] = 1

    for d in range(len(S) - 1):
        s = S[-2-d]
        if s == "?":
            tmp = dic[R[d+1]]
            for key in tmp.keys():
                for i in range(13):
                    memo[d + 1][(key + i)%13] = (dic[R[d+1]][key]*(memo[d][i] + memo[d + 1][(key + i)%13]))%mod
        else:
            for i in range(13):
                memo[d + 1][(i + int(s)*R[d+1])%13] = (memo[d][i] + memo[d + 1][(i + int(s)*R[d+1])%13])%mod
    print(memo[len(S) - 1][5])
    return

if __name__ == "__main__":
    main()

Solution (Python):
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] %= 10**9 + 7
    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] %= 10**9 + 7
    mul = mul * 10 % 13

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

Solution (Python):
S = list(input())
S.reverse()
N = len(S)
mod = 10**9+7
dp = [[0 for r in range(13)] for n in range(N+1)]
dp[0][0] = 1
lookup = [[0 for d in range(10)] for n in range(N)]
for n in range(N):
    for d in range(10):
        lookup[n][d] = d*pow(10, n, 13) % 13
for n in range(1, N+1):
    if S[n-1] == '?':
        for d in range(10):
            for r in range(13):
                dp[n][(r+lookup[n-1][d]) % 13] += dp[n-1][r] % mod
    else:
        for r in range(13):
            dp[n][(r+lookup[n-1][int(S[n-1])]) % 13] += dp[n-1][r] % mod
print(dp[-1][5] % mod)

Solution (Python):

S = input()
lenS = len(S)
DP = [0] * 13
ans = [0]*13
i_mod = [1] * lenS
if S[lenS-1] == "?":
    for j in range(10):
        ans[j % 13] += 1
else:
    ans[int(S[lenS-1]) % 13] += 1

for i in range(1, len(S)):
    DP = [0]*13
    for r in range(13):
        DP[r] += ans[r] % (10**9+7)
    ans = [0]*13
    i_mod[i] = (i_mod[i - 1] * 10) % 13
    i_now = 0
    i_now += i_mod[i]
    if S[lenS-i-1] == "?":
        for p in range(13):
            for h in range(10):
                ans[(p+h * i_now) % 13] += DP[p]

    else:
        for q in range(13):
            ans[(q+i_now * int(S[lenS-i-1])) % 13] = DP[q]


print(ans[5] % (10**9+7))

Solution (Python):
MOD=10**9+7
S=input()
N=len(S)
if N==1:
  if S=='?' or int(S)==5:
    print(1)
  else:
    print(0)
  exit()

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

Solution (Python):
MOD=10**9+7
S=input()
N=len(S)
if N==1:
  if S=='?' or int(S)==5:
    print(1)
  else:
    print(0)
  exit()

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

Solution (Python):
def dot(A, x):
  return [sum([x[t]*A[s][t] for t in range(13)]) for s in range(13)]

MOD=10**9+7

S=input()
N=len(S)
if N==1:
  if S=='?' or int(S)==5:
    print(1)
  else:
    print(0)
  exit()

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

Solution (Python):
def dot(A, x):
  return [sum([x[t]*A[s][t] for t in range(13)]) for s in range(13)]

S=input()
N=len(S)
if N==1:
  if S=='?' or int(S)==5:
    print(1)
  else:
    print(0)
  exit()

MOD=10**9+7

if S[0]=='?':
  x=[1]*10+[0]*3
else:
  x=[0]*13
  x[int(S[0])]=1
  
P=[
  [
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
  ],
  [
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
  ],
  [
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  ],
  [
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0]
  ],
  [
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
  ],
  [
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  ],
  [
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
  ],
  [
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]
  ],
  [
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  ],
  [
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 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])

Solution (Python):
def f(index, num):
  for k in range(13):
    a[index][(k*10+num)%13]+=a[index-1][k]

S=input()
N=len(S)
if N==1:
  if S=='?' or int(S)==5:
    print(1)
  else:
    print(0)
  exit()
  
MOD=10**9+7

a=[[0]*13 for i in range(N)]
if S[0]=='?':
  a[0]=[1]*10+[0]*3
else:
  a[0][int(S[0])]=1

for i in range(1, N):
  if S[i]=='?':
    for j in range(10):
      f(i, j)
    for j in range(13):
      a[i][j]%=MOD
  else:
    f(i, int(S[i]))
    
print(a[-1][5])

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

s = list(input())
n = len(s)
s = s[::-1]
dp = [[0]*13 for _ in range(n)]
if s[0] == '?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(s[0])] = 1
x = 1
for i in range(1,n):
    x = (x*10) % 13
    if s[i] == '?':
        for j in range(10):
            for k in range(13):
                dp[i][(k+(j*x) % 13) % 13] += dp[i-1][k]
                dp[i][(k+(j*x) % 13) % 13] %= mod
    else:
        y = int(s[i])
        for j in range(13):
            dp[i][(j+(y*x) % 13) % 13] += dp[i-1][j]
            dp[i][(j+(y*x) % 13) % 13] %= mod
print(dp[-1][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()
MOD = 10**9+7
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[(10*i+d)%13] += old_dp[i]
        else:
            new_dp[(10*i+int(c))%13] += old_dp[i]
    
    old_dp = [x % MOD for x in new_dp]
    new_dp = [0]*13
print(old_dp[5])

Solution (Python):
s = input()
n = len(s)
mod = 10**9+7
dp = [[0]*13 for i in range(n+5)]
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][(j*10+d)%13] += dp[i][j]
                dp[i+1][(j*10+d)%13] %= mod
                
        else:
            dp[i+1][(j*10+int(s[i]))%13] += dp[i][j]
            dp[i+1][(j*10+int(s[i]))%13] %= mod
ans = dp[n][5]
print(ans)

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

dp = [0]*13
dp[0] = 1

mul = 1
for i, s in enumerate(S[::-1]):
    new = [0]*13
    if s == "?":
        for x in range(13):
            for y in range(10):
                next_x = y * mul + x
                new[next_x % 13] += dp[x]
                new[next_x % 13] %= mod
    else:
        for x in range(13):
            next_x = int(s) * mul + x
            new[next_x % 13] = dp[x]

    dp = new
    mul *= 10
    mul %= 13

ans = dp[5] % mod
print(ans)

Solution (Python):
S=input()
N=len(S)
mod=13
mod2=10**9+7


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

dp[0][0]=1

for i in range(N):
    if S[i]!="?":
        for j in range(mod):
            dp[i+1][(10*j+int(S[i]))%mod]=dp[i][j]
    else:
        for j in range(mod):
            for k in range(10):
                dp[i+1][(10*j+k)%mod]+=dp[i][j]%mod2

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

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

Solution (Python):
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    s = str(readline().rstrip().decode('utf-8'))
    dp = [[0] * 13 for _ in range(len(s))]
    for i in range(len(s)):
        if i == 0:
            if s[-i-1] == "?":
                for j in range(10):
                    dp[i][j % 13] += 1
            else:
                t = int(s[-i-1])
                dp[i][t % 13] += 1
        else:
            md = pow(10, i, 13)
            if s[-i-1] == "?":
                for j in range(10):
                    for k in range(13):
                        dp[i][(j * md + k) % 13] += dp[i-1][k]
            else:
                t = int(s[-i-1])
                for k in range(13):
                    dp[i][(t * md + k) % 13] += dp[i - 1][k]
        for l in range(13):
            dp[i][l] %= mod
    print(dp[-1][5])


if __name__ == '__main__':
    solve()

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

Solution (Python):
S = input()
S = S[::-1]
N = len(S)

mod = 10**9 + 7

dp = [[1] + [0]*12] + [[0]*13 for i in range(N)]

digit = 1
for i, s in enumerate(S):
  if s == '?':
    R = [j*digit % 13 for j in range(10)]
    for j in range(13):
      for r in R:
        dp[i+1][(j+r)%13] = (dp[i+1][(j+r)%13] + dp[i][j]) % mod
      
  else:
    s = int(s)
    r = s*digit % 13
    dp[i+1] = dp[i][-r:] + dp[i][:-r]
  
  digit *= 10
  digit %= 13

print(dp[-1][5])

Solution (Python):

S = input()

MOD = 10 ** 9 + 7
count = 0
S_len = len(S)

dp = [[0 for i in range(13)] for j in range(100006)]
c = -1
if S[0] != '?':
    c = int(S[0])
for j in range(10):
    if c == -1:
        dp[1][j] = 1
    else:
        dp[1][c] = 1

for i in range(2, S_len + 1):
    c = -1
    if S[i - 1] != '?':
        c = ord(S[i - 1]) - ord('0')

    for j in range(10):
        if c != -1 and c != j:
            continue
        for k in range(13):
            dp[i][(k * 10 + j) % 13] += dp[i - 1][k] % MOD


print(dp[S_len][5] % MOD)

Solution (Python):
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]
    c = [int(c)] if c != '?' else range(10)

    for k in c:
        for j in range(13):
            dp[i + 1][(j * 10 + k) % 13] += dp[i][j]

    for j in range(13):
        dp[i + 1][j] %= mod

print(dp[N][5])

Solution (Python):
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]
    c = '?' if c == '?' else int(c)

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

    for j in range(13):
        dp[i + 1][j] %= mod

print(dp[N][5])

Solution (Python):
s = input()
dp = [[0 for j in range(13)] for _ in range(len(s) + 1)]
dp[0][0] = 1

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