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

Solution (Python):
def main():
  S = str(input())
 
  ans = [0] * 13
  ans[0] = 1
  MOD = 10**9 + 7

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

  print(ans[5] % MOD)

if __name__ == '__main__':
    main()

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

    table = [[0] * 10 for _ in range(13)]
    for i in range(13):
        for j in range(10):
            table[i][j] = (i * 10 + j) % 13

    table2 = [[] for _ in range(13)]
    for i in range(13):
        for j in range(10):
            table2[table[i][j]].append(i)
    t = set(range(13))
    table2 = [t - set(i) for i in table2]

    if S[0] == -1:
        for i in range(10):
            dp[0][i] += 1
    else:
        dp[0][S[0] % 13] += 1

    for i in range(1, s):
        if S[i] == -1:
            temp = sum(dp[i - 1])
            for j in range(13):
                dp[i][j] = temp
                for k in table2[j]:
                    dp[i][j] -= dp[i - 1][k]
                dp[i][j] %= mod
        else:
            for j in range(13):
                dp[i][table[j][S[i]]] = dp[i - 1][j]

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


if __name__ == '__main__':
    main()

Solution (Python):
S = str(input())
S_len = len(S)

DP = [[0 for j in range(13)] for i in range(S_len + 1)]
DP[S_len][0] = 1
num = 1

for i in reversed(range(S_len)):

    

    if S[i] != "?":
        for j in range(13):
            DP[i][(j + int(S[i]) * num) % 13] += DP[i + 1][j] % 1000000007
    else:
        for j in range(13):
            for k in range(10):
                DP[i][(j + k * num) % 13] += DP[i + 1][j] % 1000000007

    num = (num * 10) % 13

print(DP[0][5] % 1000000007)

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

Solution (Python):
def getlist():
	return list(map(int, input().split()))

con = 1000000007


def main():
	
	S = list(input())
	N = len(S)
	for i in range(N):
		if S[i] != "?":
			S[i] = int(S[i])
	S.reverse()
	
	
	amari = [[0] * 6 for i in range(10)]
	for i in range(10):
		for j in range(6):
			amari[i][j] = (i * (10 ** j)) % 13

	
	DP = [[0] * 13 for i in range(N + 1)]
	if S[0] == "?":
		for i in range(10):
			DP[0][i] = 1
	else:
		DP[0][S[0]] = 1
	for i in range(1, N):
		if S[i] != "?":
			A = amari[S[i]][i % 6]
			for j in range(13):
				DP[i][(A + j) % 13] += DP[i - 1][j]
				DP[i][(A + j) % 13] %= con
		else:
			for k in range(10):
				A = amari[k][i % 6]
				for j in range(13):
					DP[i][(A + j) % 13] += DP[i - 1][j]
					DP[i][(A + j) % 13] %= con

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

if __name__ == '__main__':
	main()

Solution (Python):

def main():
    S = input()

    modN = 13
    modAns = 10**9+7
    dp_table = [[0 for idx in range(modN)] for _ in range(len(S)+1)]
    dp_table[0][0] = 1

    for digit in range(len(S)):
        if S[digit] == '?':
            for mod in range(modN):
                for add_num in range(10):
                    next_mod = (10*mod + add_num) % 13
                    dp_table[digit+1][next_mod] += dp_table[digit][mod]
        else:
            val = int(S[digit])
            for mod in range(modN):
                next_mod = (10*mod + val) % 13
                dp_table[digit+1][next_mod] += dp_table[digit][mod]
        for idx in range(modN):
            dp_table[digit+1][idx] %= modAns

    print(dp_table[-1][5])


if __name__ == "__main__":
    main()

Solution (Python):





S = input()

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

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

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

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

Solution (Python):
def main():
    sts=input()
    n= len(sts)
    mod = 10**9+7
    s = []
    for c in sts:
        s.append(c)

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

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

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


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

main()

Solution (Python):
def slove():
    import sys
    input = sys.stdin.readline
    s = str(input().rstrip('\n'))
    is_first = True
    ls = [[0] * 13 for _ in range(len(s))]
    mod = 10 ** 9 + 7
    for i in range(len(s)):
        if is_first:
            is_first = False
            if s[-i-1] == "?":
                for j in range(10):
                    ls[i][j] += 1
            else:
                t = int(s[-i-1])
                ls[i][t] += 1
        else:
            mlt = pow(10, i, 13)
            if s[-i-1] == "?":
                for j in range(13):
                    for k in range(10):
                        r = (j + mlt * k) % 13
                        ls[i][r] += ls[i-1][j]
                        ls[i][r] %= mod
            else:
                t = int(s[-i-1])
                for j in range(13):
                    r = (j + mlt * t) % 13
                    ls[i][r] += ls[i-1][j]
                    ls[i][r] %= mod
    print(ls[-1][5])


if __name__ == '__main__':
    slove()

Solution (Python):
s = str(input())
mod = 10**9 + 7
n = len(s)

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


for i in s[1:]:
  dp = [0]*13
  for j in range(13):
    dp[j*10%13] = ans[j] % mod
  dp += dp
  if i == "?":
    for j in range(13):
      ans[j] = sum(dp[j+4:j+14])
  else:
    for j in range(13):
      ans[j] = dp[j+13-int(i)]
print(ans[5]%mod)

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

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

n = len(S)
for i in range(n):
    if i == 0:
        mod_array = [i for i in range(10)]
    else:
        mod_array = [i * 10 % 13 for i in mod_array]
    s = S[n-i-1]
    if s == '?':
        for a in mod_array:
            for k in range(13):
                dp[1][(k+a)%13] += dp[0][k]
    else:
        a = mod_array[int(s)]
        for k in range(13):
            dp[1][(k + a) % 13] += dp[0][k]
    for k in range(13):
        dp[0][k] = dp[1][k] % MOD
        dp[1][k] = 0

print(dp[0][5])

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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

MOD = 10**9 + 7

S = read().rstrip().decode('utf-8')

num = [0,0,0,0,0,0]
ques = [0,0,0,0,0,0]
for i,x in enumerate(S[::-1]):
    i %= 6
    if x == '?':
        ques[i] += 1
    else:
        num[i] += int(x)

ten = np.array([1]*10+[0,0,0],dtype=np.uint64)

def power(n):
    
    if n == 0:
        x = np.zeros(13,dtype=np.uint64)
        x[0] = 1
        return x
    x = power(n//2)
    x = np.convolve(x,x) % MOD
    x[0:12] += x[13:25]; x = x[:13]; x[x>=MOD] -= MOD
    if n&1:
        x = np.convolve(x,ten)
        x[0:12] += x[13:25]; x = x[:13]; x %= MOD
    return x

dp = [power(n) for n in ques]

pow10 = [1,10,9,12,3,4]

x = power(0)
for i,y in enumerate(dp):
    p = pow10[i]
    y[p*np.arange(13)%13] = y.copy()
    x = np.convolve(x,y) % MOD
    x[0:12] += x[13:25]; x = x[:13]; x[x>=MOD] -= MOD

n = sum(p*n for p,n in zip(pow10,num))%13

answer = x[(18-n)%13]
print(answer)

Solution (Python):
MOD = 1000000007
S = input()
memo = [[0] * 13 for i in range(len(S)+1)]
memo[0][0] = 1

for idx in range(len(S)):
	ch = S[idx]
	if(ch == '?'):
		for num in range(10):
			for i in range(13):
				if(memo[idx][i] > 0):
					memo[idx+1][(i*10+num)%13] += memo[idx][i] 
	else:
		num = int(ch)
		for i in range(13):
			if(memo[idx][i] > 0):
				memo[idx+1][(i*10+num)%13] += memo[idx][i] 
	
	for i in range(13):
		memo[idx+1][i] %= MOD

print(memo[len(S)][5]%MOD)

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
table = {str(i):[(10*j+i)%13 for j in range(13)] for i in range(10)}
for k in range(1,len(S)):
  tmp = dp[k-1]
  if S[k] != "?":
    for i,t in enumerate(table[S[k]]):
      dp[k][t]= tmp[i]
  else:
    for j in range(10):
      for i,t in enumerate(table[str(j)]):
        dp[k][t] += tmp[i]%mod
    dp[k] = [p%mod for p in dp[k]]
print(dp[-1][5])

Solution (Python):
def main():
    S = input()

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

    mul = 1

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


    print(dp[5])


if __name__ == '__main__':
    main()

Solution (Python):
S = str(input())

ans = [0] * 13
ans[0] = 1
MOD = 10**9 + 7

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

print(ans[5] % MOD)

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

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

Solution (Python):
S = list(input())
for i in range(len(S)):
    if S[i] != '?':
        S[i] = int(S[i])
    else:
        S[i] = -1

R = [[None]*10 for i in range(13)]
for i in range(13):
    for j in range(10):
        R[i][j] = (10*i+j) % 13

Q = [[] for i in range(13)]
for j in range(10):
    for i in range(13):
        Q[R[i][j]] += [[i,j]]

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

for i in range(len(S)):
    for j in range(13):
        if S[i]!=-1:
            dp[i+1][j] += dp[i][Q[j][S[i]][0]]%1000000007
        else:
            for k in range(10):
                dp[i+1][j] += dp[i][Q[j][k][0]]%1000000007

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

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
s=input()
mod=10**9+7
cnt=[[0]*13 for i in range(len(s))]
if s[0]=="?":
    for i in range(10):  
        cnt[0][i]+=1
else:
    cnt[0][int(s[0])]+=1

n=len(s)
for i in range(1,n):
    if s[i]=="?":
        now=-1
    else:
        now=int(s[i])
    if now==-1:
        for j in range(13):
            for k in range(10):
                cnt[i][(j*10+k)%13]+=cnt[i-1][j]
                cnt[i][(j*10+k)%13]%=mod
    else:
        for j in range(13):
            cnt[i][(j*10+now)%13]+=cnt[i-1][j]
            cnt[i][(j*10+now)%13]%=mod


print(cnt[n-1][5]%mod)

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

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


s = ns()
n = len(s)

TEN = 10
THIRTEEN = 13
MOD = 10**9 + 7
dp = [[0]*THIRTEEN for _ in range(n+1)]
dp[0][0] = 1

for i, si in enumerate(s):
    if si == "?":
        for k in range(TEN):
            for j in range(THIRTEEN):
                dp[i + 1][(10*j + k) % THIRTEEN] += dp[i][j]
                dp[i + 1][(10*j + k) % THIRTEEN] %= MOD

    else:
        k = int(si)
        for j in range(THIRTEEN):
            dp[i + 1][(10*j + k) % THIRTEEN] += dp[i][j]
            dp[i + 1][(10*j + k) % THIRTEEN] %= MOD

print(dp[n][5])

Solution (Python):
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac
import bisect
import heapq

import logging
logging.basicConfig(level=logging.DEBUG)

import sys
input = sys.stdin.readline().rstrip

setrecursionlimit(1000000)

MOD = 10**9+7
INF = float('inf')

def main():
    S=input()

    dp = [[0] * 13 for _ in range(len(S)+1)] 
    dp[0][0]=1
    for k in range(len(S)):
        c=S[k]
        
        if c=="?":
            for i in range(13):
                for j in range(10):
                    dp[k+1][(i*10+j)%13]+=dp[k][i]
                    dp[k+1][(i*10+j)%13]%=MOD
        else:
            for i in range(13):
                dp[k+1][(i*10+int(c))%13]+=dp[k][i]
                dp[k+1][(i*10+int(c))%13]%=MOD
    
    print(dp[len(S)][5])

main()

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

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

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

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

def main():
    s = [int(in_i) if in_i != '?' else -1 for in_i in list(open(0).read())[:-1]]
    n = len(s)

    cnt = [0] * 13
    if s[0] == -1:
        for j in range(10):
           cnt[j] = 1
    else:
        cnt[s[0]] = 1

    for cur_s in s[1:]:
        dp = [0] * 26
        for i in range(13):
            dp[i*10%13] = cnt[i] % MOD
        dp[13:] = dp[:13]

        if cur_s == -1:
            for i in range(13):
                cnt[i] = sum(dp[i+4:i+14])
        else:
            for i in range(13):
                cnt[i] = dp[i+13-cur_s]

    ans = cnt[5] % MOD
    print(ans)
    return()

if __name__ == '__main__':
    main()

Solution (Python):
S = input()

rs = [0] * 13

M = 10**9 + 7

if S[-1] == "?":
    rs[:10] = [1] * 10
else:
    rs[int(S[-1])] = 1

for i in range(1, len(S)):
    nrs = [0] * 13
    c = S[-i - 1]
    if c == "?":
        ns = range(10)
    else:
        ns = [int(c)]
    for n in ns:
        r = (10 ** (i % 6)) * n % 13
        for j in range(13):
            jj = (j + r) % 13
            nrs[jj] = (nrs[jj] + rs[j]) % M
    rs = nrs


print(rs[5])

Solution (Python):
MOD = 1000000007
s = [int(x) if x!="?" else -1 for x in input()]
dp = [[0] *  13 for _ in range(len(s))] 

if s[0] == -1:
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(s[0])] = 1
 
table = [ s % 13 for s in range(130)]
for index in range(1, len(s)):
    if not s[index] == -1:
        value = int(s[index])
 
        for old_amari in range(13):
            new_amari = (table[old_amari * 10] + value) % 13
            dp[index][new_amari] += dp[index-1][old_amari]
    else:
        for value in range(10):
            for old_amari in range(13):
                new_amari = (table[old_amari * 10] + value) % 13
                dp[index][new_amari] += dp[index - 1][old_amari]
 
    for i in range(len(dp[index])):
        dp[index][i] %= MOD

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

Solution (Python):
def slove():
    import sys
    input = sys.stdin.readline
    s = [int(i) if i != "?" else -1 for i in list(str(input().rstrip('\n')))]
    ls = [[0] * 13 for _ in range(len(s))]
    mod = 10 ** 9 + 7
    for i in range(1):
        if s[-i-1] != -1:
            ls[i][s[-i-1] % 13] = 1
        else:
            for j in range(10):
                ls[i][j % 13] = 1
    for i in range(1, len(s)):
        mult = pow(10, i, 13)
        if s[-i-1] == -1:
            for j in range(10):
                for k in range(13):
                    ls[i][(mult * j + k) % 13] += ls[i-1][k]
                    ls[i][(mult * j + k) % 13] %= mod
        else:
            for k in range(13):
                ls[i][(mult * s[-i-1] + k) % 13] += ls[i-1][k]
                ls[i][(mult * s[-i-1] + k) % 13] %= mod
    print(ls[-1][5])


if __name__ == '__main__':
    slove()

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

Solution (Python):
inf = 10**9+7
modlist = [1, 10, 9, 12, 3, 4]

S = list(input())
S.reverse()

dp = [[0 for i in range(13)] for j 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 l in range(10):
        if S[i] != "?" and int(S[i]) != l:
            continue
        for j in range(13):
            dp[i][(l*modlist[i%6]+j)%13] += dp[i-1][j]
            dp[i][(l*modlist[i%6]+j)%13] %= inf

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

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

amari=[[(10**i)*x%13 for x in range(10)] for i in range(6)]
dp=[1]+[0]*12
new_dp=[0]*13

mod=10**9+7

for id,char in enumerate(s):
    new_dp=[0]*13
    if char!='?':
        for i in range(13):
            new_i=(i+amari[id%6][int(char)])%13
            new_dp[new_i]+=dp[i]
        dp=new_dp
    else:
        for i in range(13):
            for j in range(10):
                new_i=(i+amari[id%6][j])%13
                new_dp[new_i]+=dp[i]
        dp=[x%mod for x in new_dp]
print(dp[5])

Solution (Python):
def main():
    MOD = 7 + 10**9
    S = tuple(input())
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] += 1
    s=[1]
    for n in range(1,N):
        s.append((s[n-1]*10)%13)
    for i in range(N):
        for k in range(13):
            if S[-(i+1)] != '?':
                dp[i+1][(k+int(S[-(i+1)])*s[i])%13] += dp[i][k] 
                dp[i+1][(k+int(S[-(i+1)])*s[i])%13] %= MOD
            else:
                for l in range(10):
                    dp[i+1][(k+l*s[i])%13] += dp[i][k]
                    dp[i+1][(k+l*s[i])%13] %= MOD
    print(dp[-1][5])

if __name__ == '__main__':
    main()

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

Solution (Python):
S = input()
p = 10 ** 9 + 7
DP = [[0 for _ in range(13)] for _ in range(len(S) + 1)]
DP[0][0] = 1
M = [[0 for _ in range(13)] for _ in range(6)]
for i in range(6):
  for j in range(10):
    M[i][j] = j * 10 ** i % 13
for i, s in enumerate(S[::-1]):
  if s == '?':
    for j in range(10):
      m = M[i % 6][j]
      for k in range(13):
        DP[i + 1][(k + m) % 13] += DP[i][k]
  else:
    m = M[i % 6][int(s)]
    for k in range(13):
      DP[i + 1][(k + m) % 13] += DP[i][k]
  for k in range(13):
    DP[i + 1][k] %= p
print(DP[-1][5])

Solution (Python):
s=input()
l=len(s)
mod = pow(10,9)+7

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

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

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):
"""
この解答に自分用にコメントつけただけ
https://atcoder.jp/contests/abc135/submissions/6585300
"""

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

    dp[0][0] = 1 

    """
    たとえば５６７８という数字について考えるとき
    5：s[1][5] = 1で他のjが０
    56：5 -> 56なので、 dp[2][(5*10 + 6) % 13] += dp[1][5]
    先頭からi文字目まで見たときに余りが５となる数字列について、一桁増えると余りも一桁増える＆新たに増えた桁との和のさらにあまりが新たにできた数字の余り
    """

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

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

if __name__ == "__main__":
    main()

Solution (Python):
def slove():
    import sys
    input = sys.stdin.readline
    s = [int(v) if v != "?" else -1 for v in list(str(input().rstrip('\n')))]
    dp = [[0] * 13 for _ in range(2)]
    mod = 10 ** 9 + 7

    for i in range(1):
        if s[-i-1] == -1:
            for j in range(10):
                dp[0][j % 13] += 1
        else:
            dp[0][s[-i - 1] % 13] += 1

    for i in range(1, len(s)):
        m = pow(10, i, 13)
        if s[-i-1] == -1:
            for j in range(10):
                mj = m * j
                for k in range(13):
                    dp[1][(mj + k) % 13] += dp[0][k]
        else:
            for k in range(13):
                dp[1][(m * s[-i-1] + k) % 13] += dp[0][k]
        for j in range(13):
            dp[0][j] = dp[1][j] % mod
            dp[1][j] = 0
    print(dp[0][5] % mod)


if __name__ == '__main__':
    slove()

Solution (Python):
def slove():
    import sys
    input = sys.stdin.readline
    s = [int(v) if v != "?" else -1 for v in list(str(input().rstrip('\n')))]
    dp = [[0] * 13 for _ in range(2)]
    mod = 10 ** 9 + 7

    for i in range(1):
        if s[-i-1] == -1:
            for j in range(10):
                dp[0][j % 13] += 1
        else:
            dp[0][s[-i - 1] % 13] += 1

    for i in range(1, len(s)):
        m = pow(10, i, 13)
        if s[-i-1] == -1:
            for j in range(10):
                mj = m * j
                for k in range(13):
                    dp[1][(mj + k) % 13] += dp[0][k]
        else:
            for k in range(13):
                dp[1][(m * s[-i-1] + k) % 13] += dp[0][k]
        for j in range(13):
            dp[0][j] = dp[1][j] % mod
            dp[1][j] = 0
    print(dp[0][5] % mod)


if __name__ == '__main__':
    slove()

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

Solution (Python):
import numpy as np
MOD=10**9+7

S=[int(x) if x != "?" else -1 for x in input()]
N=len(S)


r=[0]*13


s=S[0]
if s != -1:
  r[s] = 1
else:
  for i in range(10):
    r[i] = 1


for i in range(1,N):
  
  
  dp = [0]*26
  
  for j in range(13):
    dp[j*10%13] += r[j] % MOD
  
  dp[13:26] = dp[0:13]
  r=[0]*13
  s=S[i]
  if s == -1:
    w=sum(dp[4:14])
    for j in range(13):
      r[j] += w
      w += dp[j+1] -dp[j+4]
  else:
    for j in range(13):
      r[j] += dp[13-s+j]
print(r[5]%MOD)

Solution (Python):
S = input()
dp0 = [0]*13
dp0[0] = 1
dp = [dp0]

for i in range(len(S)):
  dpi = dp[i]
  dpn = [0]*13
  c = S[i]
  e = (10**((len(S)-i-1)%12))%13
  if c == "?":
    for j in range(13):
      r = 0
      for d in range(10):
        r += dpi[(j+13-d*e)%13]
      dpn[j] = r%1000000007
  else:
    d = int(c)
    for j in range(13):
      dpn[j] = dpi[(j+13-d*e)%13]
  
  dp.append(dpn)
print(dp[len(S)][5])

Solution (Python):

import sys


MOD = 1000000007  


def solve(S: str):
    
    dp = [[0 for j in range(13)] for i in range(len(S) + 1)]
    dp[0][0] = 1
    for i in range(len(S)):
        if S[i] == '?':
            for j in range(10):
                for k in range(13):
                    dp[i + 1][(k * 10 + j) % 13] += dp[i][k] % MOD
        else:
            j = int(S[i])
            for k in range(13):
                dp[i + 1][(k * 10 + j) % 13] += dp[i][k] % MOD
    print(int(dp[-1][5]) % MOD)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  
    solve(S)

if __name__ == '__main__':
    main()

Solution (Python):
MOD = 10**9 + 7
def dp(a):
    L = len(a)

    dp = [[0 for j in range(13)] for k in range(L + 1)]
    dp[0][0] = 1
    for i in range(L):
        if a[i] == "?":
            for j in range(10):
                for k in range(13):
                    dp[i + 1][(j + k*10) % 13] += dp[i][k]
                    dp[i + 1][(j + k*10) % 13] %= MOD
        else:
            for k in range(13):
                dp[i + 1][(int(a[i])+k*10) % 13] += dp[i][k]
                dp[i + 1][(int(a[i])+k*10) % 13] %= MOD
    print(dp[L][5] % MOD)


def main():
    S = input()
    dp(S)


if __name__ == '__main__':
    main()

Solution (Python):
MOD = 10**9 + 7
def dp(a):
    L = len(a)

    dp = [[0 for j in range(13)] for k in range(L + 1)]
    dp[0][0] = 1
    for i in range(L):
        if a[i] == "?":
            for j in range(10):
                for k in range(13):
                    dp[i + 1][(j + k*10) % 13] += dp[i][k]
                    dp[i + 1][(j + k*10) % 13] %= MOD
        else:
            for j in range(13):
                dp[i + 1][(int(a[i])+j*10) % 13] += dp[i][j]
                dp[i + 1][(int(a[i])+j*10) % 13] %= MOD
    print(dp[L][5] % MOD)


def main():
    S = input()
    dp(S)


if __name__ == '__main__':
    main()

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

Solution (Python):
S = input()
 
MOD = 10**9+7
 
dp = [[0]*13 for _ in range(len(S) + 1)]
 
 
dp[0][0] = 1
 
mul = 1
for index in range(len(S)):
    s = S[len(S) - index - 1]
    if s == '?':
        for pre_index in range(13):
            for i in range(10):
                next_i = (i * mul +  pre_index ) % 13
                dp[index+1][next_i] += dp[index][pre_index] 
                dp[index+1][next_i] %= MOD

    else:
        for pre_index in range(13):
            i = int(s)
            next_i = (i * mul  +  pre_index ) % 13
            dp[index+1][next_i] += dp[index][pre_index] 
            dp[index+1][next_i] %= MOD
    mul *= 10
    mul %= 13
 
 
 
print(dp[len(S)][5])