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

def solve():
    S = input()
    mod = 7 + 10 ** 9
    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:
            k = int(S[i])
            for j in range(13):
                DP[i][(j * 10 + k) % 13] += DP[i-1][j]
                DP[i][(j * 10 + k) % 13] %= mod
    print(DP[len(S) - 1][5])

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
S = input()
ans = [[0] * 13 for _ in range(len(S))]
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, s in enumerate(S):
    if i == 0:
        continue
    if s == "?":
        for n in range(10):
            for j in range(13):
                ans[i][(j * 10 + n) % 13] += ans[i - 1][j]
                ans[i][(j * 10 + n) % 13] %= MOD
    else:
        for j in range(13):
            ans[i][(j * 10 + int(s)) % 13] = ans[i - 1][j]

print(ans[-1][5])

Solution (Python):
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10

MOD = 10 ** 9 + 7


S = [c for c in stdin.readline().rstrip()]
N = len(S)




dp = [[0] * 13 for _ in range(10**5+5)]

dp[0][0] = 1

for i in range(N):
    c = 0
    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] %= MOD


ans = dp[N][5]

print(ans)

Solution (Python):
def main():
    s = input().strip()

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

    power = 1
    mod = 10 ** 9 + 7
    for c in reversed(s):
        ndp = [0] * 13
        for rem in range(13):
            candidate = range(10) if c == '?' else [int(c)]
            for digit in candidate:
                nrem = (rem + digit * power) % 13
                ndp[nrem] = (ndp[nrem] + dp[rem]) % mod
        dp = ndp
        power = (power * 10) % 13
    print(dp[5])


if __name__ == '__main__':
    main()

Solution (Python):

mod = 10 ** 9 + 7
S = input()[::-1]
W = [1, 10, 9, 12, 3, 4]

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

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

    w = W[i % 6]
    if s == "?":
        for n in range(10):
            r = (n * w) % 13
            for j in range(13):
                dp[i][(j + r) % 13] = (dp[i][(j + r) % 13] + dp[i - 1][j]) % mod

    else:
        n = int(s)
        r = (n * w) % 13
        for j in range(13):
            dp[i][(j + r) % 13] = (dp[i][(j + r) % 13] + dp[i - 1][j]) % mod

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

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

Solution (Python):
S=input()
N=len(S)
from collections import defaultdict
O=[defaultdict(int) for i in range(N+1)]
O[0][5]=1
mod=10**9+7
for i in range(N):
    for o in O[i].keys():
        if S[N-1-i]!='?':
            n=int(S[N-1-i])
            for j in range(10):
                x=13*j+o
                if x%10==n:
                    O[i+1][x//10]=O[i][o]
                    break
        else:
            for j in range(10):
                x=13*j+o
                O[i+1][x//10]=(O[i+1][x//10]+O[i][o])%mod
print(O[N][0])

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

MOD = pow(10, 9) + 7

def main():
  s = input().strip()
  sd = [[0 for _ in range(13)] for _ in range(len(s))]
  if s[-1] == '?':
    for i in range(10):
      sd[0][i] = 1
  else:
    sd[0][int(s[-1])] = 1

  for i, _s in enumerate(s[::-1]):
    if i == 0:
      continue
    if _s != '?':
      rem = int(_s) * pow(10, i, 13) % 13
      for j in range(13):
        sd[i][(j+rem)%13] = sd[i-1][j]
    else:
      for k in range(10):
        rem = k * pow(10, i, 13) % 13
        for j in range(13):
          sd[i][(j+rem)%13] += sd[i-1][j]
          sd[i][(j+rem)%13] %= MOD
  print(sd[len(s)-1][5])


if __name__ == '__main__':
  main()

Solution (Python):


import math
import sys
import itertools
divisor = 1000000007

s = list(input())
t = []

for i in range( len(s) ):
    if s[i] == '?':
        t.append(-1)
    else:
        t.append(int(s[i]))

dp = [[0 for i in range(13)] for i in range(100005)]
dp[0][0]=1
for i in range(len(s)):
    for j in range(10):
        if t[i] == -1 or t[i] == j:
            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] % divisor

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

Solution (Python):
S = input()

MOD = 10 ** 9 + 7
MAX_LEN = len(S)
dp = [[0] * 13 for _ in range(MAX_LEN + 1)]
dp[0][0] = 1

for i in range(MAX_LEN):
    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):
            idx = (k * 10 + j) % 13
            dp[i + 1][idx] += dp[i][k]
            dp[i + 1][idx] %= MOD
        
print(dp[-1][5])

Solution (Python):

import sys

S =  sys.stdin.readline()[:-1]
l = len(S)

S = list(reversed(S))

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

for keta in range(len(S)):
    c =S[keta]

    if c == "?":
        for j in range(0,10):
            kurai %= 13
            temp = (j * kurai) % 13
            for i in range(13):
                dp[keta + 1][(temp + i) % 13] += (dp[keta][i] )
                dp[keta + 1][(temp + i) % 13] %= MOD
    else:
        kurai %= 13

        temp = (int(c) * kurai) % 13
        for i in range(13):
            dp[keta + 1][(temp + i) % 13]  += (dp[keta][i] )
            dp[keta + 1][(temp + i) % 13] %= MOD
    kurai *= 10
    keta %= MOD
print(dp[-1][5] )

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

shift = [(i*10)%13 for i in range(10)]

def main():
    S_tmp = input()
    N = len(S_tmp)-1
    S = [S_tmp[i] for i in range(N)]                          
    
    ans = [0]*13
    ans[0] = 1
    
    for i in range(N):
        ans_pre = [x for x in ans]
        ans = [0]*13
        
        if S[i] == "?":                   
            for j in range(13):                   
                for k in range(10):                           
                    ans[(j*10+k)%13] += ans_pre[j]
        else:       
            for j in range(13):
                ans[(j*10+int(S[i]))%13] += ans_pre[j]
                
        for j in range(13):
            ans[j] %= 10**9+7
            
    print(ans[5])
                
    

if __name__ == '__main__':
    main()

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

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

Solution (Python):
import numpy as np
from numpy.fft import fft, ifft

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

ress = [[(10 ** i * j) % 13 for j in range(10)] for i in range(6)]


state = np.zeros(13)
state[0] = 1
state = fft(state)

keta = 0
res = 5
for s in reversed(S):
    if s == "?":
        state = state * mat[keta]
    else:
        res -= ress[keta][int(s)]

    if keta == 5:
        keta = 0
        state = fft(np.remainder(np.round(np.real(ifft(state))), mod))
    else:
        keta += 1


state = ifft(state)
print(int(np.round(np.real(state[res % 13]))) % mod)

Solution (Python):


s = input()
buf = [0 for i in range(13)]
s = s[::-1]
n = len(s)


base = 10

if s[0] == "?":
    buf = [1,1,1,1,1,1,1,1,1,1,0,0,0]
else:
    buf[int(s[0])] = 1


for i in range(1,n):
    base = base%13
    nbuf = [0 for j in range(13)]
    if s[i] == "?":
        ooo = [0 for j in range(13)]
        for j in range(10):
            temp = (base*j)%13
            ooo[temp] += 1
        
        for j in range(13):
            for k in range(13):
                temp = (j+k)%13
                nbuf[temp]+= buf[k]*ooo[j]
                nbuf[temp] %= (10**9+7)
    else:
        for j in range(13):
            temp = j+int(s[i])*base
            temp %= 13
            nbuf[temp] += buf[j]
            nbuf[temp] %= (10 ** 9 + 7)
    base *= 10
    buf = nbuf
    
    


print(buf[5])

Solution (Python):
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):
  r=pow(10,n-1-i,13)
  if s[i]=="?":
    for j in range(10):
      rr=(r*j)%13
      for k in range(13):
        if k>=rr:
          DP[i+1][k]+=DP[i][k-rr]
        else:
          DP[i+1][k]+=DP[i][k-rr+13]
        DP[i+1][k]%=mod
  else:
    rr=(r*int(s[i]))%13
    for k in range(13):
      if k>=rr:
        DP[i+1][k]+=DP[i][k-rr]
      else:
        DP[i+1][k]+=DP[i][k-rr+13]
      DP[i+1][k]%=mod
print(DP[n][5]%mod)

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

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
mod = 10**9+7
def l(): 
	return list(map(int,input().split()))
def m(): 
	return map(int,input().split())
def onem(): 
	return int(input())
def s(x): 
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): 
	return " ".join(map(str,x))
def max2(x): 
	return max(map(max,x))

n = list(input())
n.reverse()
nnn = len(n)
di = 1
dp = [0 for i in range(13)]
d = [0 for i in range(13)]

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

for i in range(1,nnn):
	dp = [0 for i in range(13)]
	di *= 10
	di %= 13
	if n[i] == "?":
		for j in range(10):
			j = j * di
			j %= 13
			for kk in range(13):
				dp[(j + kk)%13] += d[kk]
				dp[(j + kk)%13] %= mod
	else:
		k = int(n[i])
		k = k * di
		k %= 13
		for kk in range(13):
			dp[(k + kk)%13] += d[kk]
			dp[(k + kk)%13] %= mod
	d = dp[:]
print(d[5]%mod)

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

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

S = input()[:-1]

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


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

print(dp[-1][5])

Solution (Python):
s = input()
s_base = int(s.replace('?', '0'))
digit = reversed(list(s))
sumd = 0
s10 = 4 
hatena = []
for i, x in enumerate(digit):
    s10 = (10 * s10) % 13
    if x == '?':
        hatena.append(s10)
    else:
        sumd += int(x) * s10
        sumd %= 13


mod = 10**9 + 7

dp = [[0] * 13 for _ in range(len(hatena) + 2)]

dp[0][0] = 1

for i in range(len(hatena)):
    for x in range(13):
        for num in range(10):
            j = (x + num*hatena[i]) % 13
            dp[i+1][j] += dp[i][x]
            dp[i+1][j] %= mod

print(dp[len(hatena)][(5-sumd)%13])
"""
print(hatena)
print(sumd)
print(dp)
"""

Solution (Python):
def main():
    mod=1000000007
    s=input()
    l=len(s)
    DP=[[0]*13 for _ in range(l+1)]
    DP[0][0]=1
    for i in range(1,l+1):
        d=s[-i]
        tmp=pow(10,i-1,13)
        if d=='?':
            for j in range(10):
                for k in range(13):
                    m=(k+tmp*j)%13
                    DP[i][m]+=DP[i-1][k]
                    if DP[i][m]>=mod:
                        DP[i][m]-=mod
        else:
            d=int(d)
            for k in range(13):
                m=(k+tmp*d)%13
                DP[i][m]+=DP[i-1][k]
                if DP[i][m]>=mod:
                    DP[i][m]-=mod
    print(DP[-1][5])

if __name__ == '__main__':
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
MOD = 10**9+7


def brute():
    S = input()[:-1]
    print(S)

    Q = [""]
    for c in reversed(S):
        tmp = []
        if c == "?":
            print("?")
            for q in Q:
                for i in range(0, 10):
                    tmp.append(str(i)+q)
        else:
            for q in Q:
                tmp.append(c+q)
        Q = tmp

    Q = sorted(Q)
    cnt = 0
    for q in Q:
        if int(q) % 13 == 5:
            cnt += 1
            print(int(q))
    print(cnt)
    print(cnt % MOD)


def solve():
    S = input()[:-1]
    
    dp = [[0]*13 for _ in range(len(S)+1)]
    dp[0][0] = 1

    S = list(reversed(S))
    for i in range(len(S)):
        if S[i] == "?":
            
            dig = pow(10, i, 13)
            for k in range(10):
                for j in range(13):
                   
                    dp[i+1][(k*dig+j) % 13] += dp[i][j]
                    dp[i+1][(k*dig+j) % 13] %= MOD

            pass
        else:
            dig = pow(10, i, 13)
            
            for j in range(13):
                dp[i+1][(int(S[i])*dig+j) % 13] += dp[i][j]
                
                dp[i+1][(int(S[i])*dig+j) % 13] %= MOD

    ans = dp[-1][5]
    print(ans)


solve()

Solution (Python):
MOD = 10 ** 9 + 7
S = input()
if S[-1] == '?':
  dp = [1,1,1,1,1,1,1,1,1,1,0,0,0]
  dpsum = 10
else:
  dp = [0] * 13
  dp[int(S[-1])] = 1
  dpsum = 1

unitmod = 1
for i, c in enumerate(list(reversed(S))[1:]):
  ndp = [0] * 13
  ndpsum = 0
  unitmod = unitmod * 10 % 13
  if c == '?':
    s = set([1,2,3,4,5,6,7,8,9,10,11,12])
    tm = unitmod
    for _ in range(9):
      s.discard(tm)
      tm = (tm + unitmod) % 13
    for j in range(13):
      x = dpsum
      for e in s:
        x -= dp[(j-e) % 13]
        x %= MOD
      ndp[j] = x
      ndpsum += x
  else:
    mod = unitmod * int(c) % 13
    for j in range(13):
      x = dp[(j-mod) % 13]
      x %= MOD
      ndp[j] = x
      ndpsum += x
  dp = ndp
  dpsum = ndpsum % MOD
print(dp[5])

Solution (Python):
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
  if t[d]=='?':
    for x in range(z):
      r=int(x)*pow(z,d,k)
      for i in range(k):
        p[(i+r)%k]+=dp[i]
  else:
    r=int(t[d])*pow(z,d,k)
    for i in range(k):
      p[(i+r)%k]+=dp[i]
  dp=[j%m for j in p]
print(dp[5]%m)

Solution (Python):
info = [[[[0] * 13 for i in range(11)] for j in range(11)] for k in range(11)]
memo = [0 for i in range(13)]
memo2 = [0 for i in range(13)]
memo2[0] = 1
memo3 = [0 for i in range(13)]
memo3[0] = 1

s = input()
if len(s) % 3 > 0:
  s = "0" * (3 - len(s) % 3) + s

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

for i in range(10):
  for j in range(10):
    for k in range(10):
      for l in range(13):
        info[10][j][k][l] += info[i][j][k][l]

for i in range(11):
  for j in range(10):
    for k in range(10):
      for l in range(13):
        info[i][10][k][l] += info[i][j][k][l]

for i in range(11):
  for j in range(11):
    for k in range(10):
      for l in range(13):
        info[i][j][10][l] += info[i][j][k][l]

v = [s[i: i+3] for i in range(0, len(s), 3)]
v.reverse()

for i in range(len(v)):
  for j in range(13):
    memo[j] = info[10 if v[i][0] == "?" else int(v[i][0])][10 if v[i][1] == "?" else int(v[i][1])][10 if v[i][2] == "?" else int(v[i][2])][j]
    memo2[j] = 0
  for j in range(13):
    for k in range(13):
      if i % 2 == 1:
        memo2[(j - k) % 13] += memo3[j] * memo[k]
      else:
        memo2[(j + k) % 13] += memo3[j] * memo[k]
  for j in range(13):
    memo2[j] = memo3[j] = (memo2[j]) % (10 ** 9 + 7)

print(memo2[5])

Solution (Python):
S = input()
n = len(S)
x = 10 ** 9 + 7
a = [1,0,0,0,0,0,0,0,0,0,0,0,0]

c = [1, -3, -4, -1, 3, 4]
for i in range(n):
    b = [0] * 13
    p = i % 6
    if S[n - i - 1] == "?":
        for j in range(13):
            for k in range(10):
                b[j] += a[(j - c[p] * k) % 13]
            b[j] = b[j] % x
        a = b
    else:
        s = int(S[n - i - 1])
        for j in range(13):
            b[j] = a[(j - c[p] * s) % 13]
        a = b
print(a[5])

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

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

dp[0] = 1
for i in range(N):
    pp, dp = dp, pp
    for d in range(13):
        dp[d] = 0
    s = S[N-i-1]
    b = pow(10, i, 13)
    if s == '?':
        for d in range(13):
            for e in range(10):
                dp[(d+b*e)%13] += pp[d]
                dp[(d+b*e)%13] %= MOD
    else:
        s = int(s)
        for d in range(13):
            dp[(d+b*s)%13] += pp[d]
            dp[(d+b*s)%13] %= MOD

print(dp[5])

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

Solution (Python):
S = input()
Ls = [1, 10, 9, 12, 3, 4]  
C = 10 ** 9 + 7

L = len(S) - 1
mem = [[0 for _ in range(13)] for _ in range(len(S))]
if S[L] == '?':
    for m in range(10):
        mem[0][m] = 1
else:
    mem[0][int(S[L])] = 1

for i in range(1, len(S)):
    t = S[L - i]
    for m in range(13):
        if t == '?':
            s = 0
            for j in range(10):
                tm = m - ((Ls[i % 6] * j) % 13)
                if tm < 0:
                    tm += 13
                s += mem[i - 1][tm]
            mem[i][m] = s % C
        else:
            tm = m - ((Ls[i % 6] * int(t)) % 13)
            if tm < 0:
                tm += 13
            mem[i][m] = mem[i - 1][tm] % C
print(mem[len(S) - 1][5])

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

Solution (Python):



def coefficient(p):
    a = p % 6
    if a == 0:
        return 1
    if a == 1:
        return 10
    if a == 2:
        return 9
    if a == 3:
        return 12
    if a == 4:
        return 3
    if a == 5:
        return 4


def submit():
    s = input()
    clist = [c for c in s]
    n = len(clist)
    ansmod = 10 ** 9 + 7

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

    dp[0][0] = 1

    for i, c in enumerate(clist):
        if c == '?':
            for x in range(10):
                for y in range(13):
                    dig_mod = y
                    dig_mod += coefficient(n - i - 1) * x
                    dig_mod %= 13
                    dp[i + 1][dig_mod] += dp[i][y]
                    dp[i + 1][dig_mod] %= ansmod
        else:
            x = int(c)
            for y in range(13):
                dig_mod = y
                dig_mod += coefficient(n - i - 1) * x
                dig_mod %= 13
                dp[i + 1][dig_mod] += dp[i][y]
                dp[i + 1][dig_mod] %= ansmod

    print(dp[n][5] % ansmod)


if __name__ == '__main__':
    submit()

Solution (Python):
m=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%m for j in p]
print(dp[5]%m)

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

Solution (Python):
from collections import Counter, defaultdict

def main():
    data = list(input())
    mod = 10 ** 9 + 7

    q_num = data.count('?')

    dp = [[0 for i in range(13)] for i in range(len(data) + 1)]
    dp[0][0] = 1

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

    ans = dp[len(data)][5]
    print(ans)



if __name__ == '__main__':
    main()

Solution (Python):
import sys

MOD = 1000000007


def main():
    s = sys.stdin.readline().strip()
    dp = [[0] * 13 for _ in range(len(s))]

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

    for i in range(1, len(s)):
        if s[i] == '?':
            for num in range(10):
                for rem_prev in range(13):
                    val = rem_prev * 10 + num
                    rem_cur = val % 13
                    dp[i][rem_cur] = (dp[i][rem_cur] + dp[i-1][rem_prev]) % MOD
        else:
            s_i = int(s[i])
            for rem_prev in range(13):
                rem_cur = (rem_prev * 10 + s_i) % 13
                dp[i][rem_cur] = (dp[i][rem_cur] + dp[i-1][rem_prev]) % MOD

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


if __name__ == '__main__':
    main()

Solution (Python):


def readInts():
  return [int(s) for s in input().split(" ")]

MOD = 10 ** 9 + 7

def main():
  S = input()
  dp = [[0 for _ in range(13)] for _a in range(len(S)+1)]

  coef = 1
  dp[0][0] = 1
  for i in range(len(S)):
    c = S[len(S) - 1 - i]
    if c == '?':
      for n in range(10):
        m = (coef * n) % 13
        for k in range(13):
          dp[i+1][(m + k) % 13] += dp[i][k]
          dp[i+1][(m + k) % 13] %= MOD
    else:
      n = int(c)
      m = (coef * n) % 13
      for k in range(13):
        dp[i+1][(m + k) % 13] += dp[i][k]
        dp[i+1][(m + k) % 13] %= MOD
    coef = (coef * 10) % 13
  print(dp[len(S)][5])

if __name__ == "__main__":
  main()

Solution (Python):
S = list(input())[::-1]
Now = [0 for _ in range(13)]
Next = [0 for _ in range(13)]

if S[0] != "?":
    Next[int(S[0])] = 1
else:
    Next = [1,1,1,1,1,1,1,1,1,1,0,0,0]
Now = Next
modq = 1
for i in range(len(S)-1):
    i = i + 1
    Next = [0 for _ in range(13)]
    if S[i] != "?":
        mod = (int(S[i])*10*modq)%13
        for j in range(len(Now)):
            Next[(mod+j)%13] = (Next[(mod+j)%13] + Now[j])%(10**9+7)
        modq = (10*modq)%13
    else:
        modq = (10*modq)%13
        mod = 0
        for j in range(10):
            for k in range(len(Now)):
                Next[(mod+k)%13] = (Next[(mod+k)%13] + Now[k])%(10**9+7)
            mod = (mod + modq)%13
    Now = Next
print(Now[5])

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
 
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
 
MOD = 10 ** 9 + 7
s = input().strip()
n = len(s)
if s[-1] == "?":
    tmp = [1 for i in range(10)] + [0 for i in range(3+13*(n-1))]
 
else:
    tmp = [0 for i in range(13*n)]
    
    
    
    tmp[int(s[-1])] = 1

keta = 1
for kt, c in enumerate(s[::-1][1:]):
    keta = (keta * 10) % 13
    
    if c != "?":
        seni = int(c) * keta
        for j in range(13):
            tmp[(j + seni) % 13 + (kt + 1) * 13] += tmp[kt * 13 + j] % MOD
    else:
        for isure in range(10):
            seni = isure * keta
            for j in range(13):
                tmp[(j + seni) % 13 + (kt + 1) * 13] += tmp[kt * 13 + j] % MOD
                
 
    
    
    
print(tmp[-8] % MOD)

Solution (Python):
import sys

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    T = list(str(input().strip()))
    S = [int(t) if t != '?' else -1 for t in T]
    n = len(S)

    dp = [[0] * 13 for _ in range(n)]
    s = S.pop()
    if s < 0:
        for i in range(10):
            dp[0][i] = 1
    else:
        dp[0][s] = 1

    digit = 1
    m = 1
    while S:
        s = S.pop()
        m = (m * 10) % 13
        if s < 0:
            for k in range(10):
                M = (m * k) % 13
                for i in range(13):
                    j = (i + M) % 13
                    dp[digit][j] += dp[digit-1][i]
                    dp[digit][j] %= MOD
        else:
            M = (m * s) % 13
            for i in range(13):
                j = (i + M) % 13
                dp[digit][j] += dp[digit-1][i]
                dp[digit][j] %= MOD
        digit += 1

    return dp[n-1][5]


if __name__ == '__main__':
    print(main())

Solution (Python):
import sys
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))
from collections import deque  
from collections import defaultdict  
from heapq import heapify, heappush, heappop, heappushpop  
from bisect import bisect_left, bisect_right  
sys.setrecursionlimit(int(1e+6))
MOD = int(1e+9) + 7



def main():
    S = i2s()
    nn09 = [i for i in range(10)]
    
    DP = [0] * 13
    
    if S[-1] == '?':
        for i in nn09:
            DP[i] = 1
    else:
        DP[int(S[-1])] = 1
    d = 10
    for i in range(len(S)-2, -1, -1):
        dp2 = [0] * 13
        s = S[i]
        if s == '?':
            nn = nn09
        else:
            nn = [int(s)]
        for n in nn:
            for j in range(13):
                k = (d*n+j) % 13
                dp2[k] = (dp2[k] + DP[j]) % MOD
        DP = dp2
        d = (d*10) % 13

    
    print(DP[5])

main()

Solution (Python):

MOD = 10**9 + 7
s = list(input())[::-1]
n = len(s)
dp = [[0] * 13 for _ in range(len(s) + 1)]
if s[0] == '?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(s[0])] = 1
for i in range(n - 1):
    if s[i + 1] == '?':
        for k in range(13):
            for l in range(10):
                dp[i + 1][(k + l * 10**((i + 1) % 6)) % 13] += dp[i][k]
                dp[i + 1][(k + l * 10**((i + 1) % 6)) % 13] %= MOD

    else:
        for k in range(13):
            dp[i + 1][(k + int(s[i + 1]) * 10**((i + 1) % 6)) % 13] += dp[i][k]
            dp[i + 1][(k + int(s[i + 1]) * 10**((i + 1) % 6)) % 13] %= MOD
print(dp[n - 1][5])

Solution (Python):
def main():
    s = [-1 if c == '?' else int(c) for c in list(input())]
    MOD = 10 ** 9 + 7
    n = len(s)
    dp = [[0] * 13 for _ in range(n)]

    if s[n-1] == -1:
        for j in range(10):
            dp[0][j] = 1
    else:
        dp[0][s[n-1]] = 1
    i10 = 1
    for i in range(1, n):
        i10 = (10 * i10) % 13
        c = s[n-i-1]
        for k in range(13):
            if c == -1:
                for j in range(10):
                    m = (i10 * j + k) % 13
                    dp[i][m] += dp[i-1][k]
                    dp[i][m] %= MOD
            else:
                m = (i10 * c + k) % 13
                dp[i][m] += dp[i-1][k]
                dp[i][m] %= MOD
    print(dp[n-1][5])


main()

Solution (Python):
words = lambda t : list(map(t, input().split()))
s = input()
rs = reversed(s)

a = []
cur_mod_10_pow = 1
v = 0
for i,c in enumerate(rs):
    if c == "?":
        a.append(cur_mod_10_pow)
    else:
        v += (int(c) * cur_mod_10_pow) % 13
        v %= 13
    cur_mod_10_pow *= 10
    cur_mod_10_pow %= 13


MOD = 1000000007
prev = [0] * 13
prev[0] = 1

for aa in a:
    cur = [0 for _ in range(13)]
    for i,p in enumerate(prev):
        
        for j in range(10):
            
            cur[(i+(aa*j)) % 13] += p
            cur[(i+aa*j) % 13] %= MOD
    
    prev = cur

print(prev[(5-v)%13])