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()
con = 10**9 + 7

T = [s if s != "?" else "0" for s in S]
T = int(''.join(T))
SS = T % 13

def get_mod(S):
    c = {}
    iii = 1
    for i in range(len(S)):
        if S[len(S) - i - 1] != "?":
            iii *= 10
            iii %= 13
            continue
        c[i] = {(j * iii) % 13: 1 for j in range(0, 10)}
        iii *= 10
        iii %= 13
    return c
c = get_mod(S)

def get_tdp(pdp):
    tdp = {i: 0 for i in range(13)}
    for r in v.keys():
        for _r, _v in pdp.items():
            i = (_r + r) % 13
            tdp[i] += _v
    for i in range(13):
        tdp[i] %= con
    return tdp

pdp = {i: 0 for i in range(13)}
pdp[SS] += 1
for k, v in c.items():
    pdp = get_tdp(pdp)

ans = pdp[5]
print(ans)

Solution (Python):
s=input()
l=len(s);mod=10**9+7
dp=[[0]*13 for i in range(l)]
rem=[1,10,9,12,3,4]
for i in range(l)[::-1]:
  dig=(l-i-1)%6
  if s[i]=="?":
    if i==l-1:
      for j in range(10):
        dp[-1][(j*rem[dig])%13]=1
    else:
      for j in range(10):
        for h in range(13):
          dp[i][(h+j*rem[dig])%13]+=dp[i+1][h]
          dp[i][(h+j*rem[dig])%13]%=mod
  else:
    a=int(s[i])
    if i==l-1:
      dp[i][(a*rem[dig])%13]=1
    else:
      for j in range(13):
        dp[i][(j+a*rem[dig])%13]+=dp[i+1][j]
        dp[i][(j+a*rem[dig])%13]%=mod
print(dp[0][5])

Solution (Python):
s = input()
n = len(s)
dp = [[0] * 13 for _ in range(n)]
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,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[n-1][5]%mod)

Solution (Python):
MOD =  1000000007
res = 0
a = input()
n = len(a)
A = 13
dp=[[0 for i in range(A+1)] for j in range(n+1)]
dp[0][0] = 1
for i in range(n):
    c = 0
    if a[i] == '?': c = -1
    else: c = int(a[i])
    
    for j in range(10):
        if c != -1 and c != j: continue
        for ki in range(13):
            dp[i+1][(ki*10 + j)% 13] += dp[i][ki]
        
    for j in range(13):
        dp[i+1][j] %= MOD

print(dp[n][5])

Solution (Python):
ll = list(input())

count = {}

for i in range(13):
    count[i] = 0

count[0] = 1

for i in ll:

    new_count = {}
    
    for j in range(13):
        new_position = (j * 10) % 13
        new_count[new_position] = count[j]

    count = new_count.copy()

    new_count = {}
    
    if i.isdigit():
        i_int = int(i)
        for j in range(13):
            new_position = (i_int + j) % 13
            new_count[new_position] = count[j]
            
    else:
        for j in range(13):
            new_count[j] = 0
            
        for k in range(10):
            for j in range(13):
                new_position = (k + j) % 13
                new_count[new_position] += count[j]            
    
    count = new_count.copy()
    
    for i in range(13):
        count[i] = count[i] % (10 ** 9 + 7)
    
print(count[5])

Solution (Python):
import math
MOD = 10**9+7
s = [int(x) if x!="?" else -1 for x in input()]
n =len(s)
A=13
data=[4,3,12,9,10,1]*math.ceil(n/6)
data=data[-n:]

dp=[[0 for i in range(A+1)] for j in range(n+1)]
dp[0][0]=1

def benri(a,i,j):
	if j-a*data[i]%A>=0:
		re = j-a*data[i]%A
	else:
		re = j-a*data[i]%A+13
	return re

for i in range(n):
	for j in range(A+1):
		if s[i]!=-1:
			dp[i+1][j]=dp[i][benri(s[i],i,j)]%MOD

		else:
			for c in range(10):
				dp[i+1][j]+=dp[i][benri(c,i,j)]%MOD

			
			

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

Solution (Python):
MOD = 1000000007;
 
s = [int(x) if x!="?" else -1 for x in input()]

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

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

Solution (Python):


R10 = range(10)
R13 = range(13)

S = input()
R = [[(M-N)*4 % 13 for N in R10] for M in R13]
AM = 10**9+7

MOD =[1]+[0]*12

for D in S:
    if D == '?':
        MOD = [sum([MOD[N] for N in M])%AM for M in R]
    else:
        C = int(D)
        MOD = [MOD[M[C]] for M in R]
    


print(MOD[5])

Solution (Python):
import itertools
 
s = str(input())
 
n = len(s)
dp = [[0]*13 for i in range(n+1)]
dp[0][0] = 1

M = 1
INF = 10 ** 9 + 7
      
for i in range(n):
  if s[n-1-i] == '?':
    for k, j in itertools.product(range(10), range(13)):
      x = (j+k*M)%13
      dp[i+1][x] += dp[i][j]
      dp[i+1][x] %= INF
  else:
    for j in range(13):
      x = (j+int(s[n-1-i])*M)%13
      dp[i+1][x] += dp[i][j]
      dp[i+1][x] %= INF
  M = (M*10)%13

print(dp[-1][5])

Solution (Python):
MOD = 1000000007

s = [-1 if x == '?' else int(x) for x in input()]
n = len(s) + 1

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

r = [[(j-i)*4%13 for i in range(10)]for j in range(13)]

for i, x in enumerate(s):
    next_dp = [0] * 13
    if x == -1:
        next_dp = [sum(dp[i] for i in j) for j in r]
    else:
        next_dp = [dp[j[x]] for j in r]
    dp = [k % MOD for k in next_dp]

print(dp[5])

Solution (Python):
if __name__ == '__main__':
    MOD = 1000000007
    s = input()
    n = len(s)

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

    for i, c in enumerate(s):
        if c == "?":
            cn = -1
        else:
            cn = int(c)

        dp.append([0 for _ in range(13)])
        for j in range(10):
            if cn != -1 and cn != 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
    result = dp[n][5]

    print(result)

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

dp = [0]*13
flag = 0
for s in S:
    if flag == 0:
        if s == "?":
            dp = [1 for _ in range(10)]+[0]*3
        else:
            s = int(s)
            dp[s%13] = 1
        flag = 1
    else:
        prev = dp
        dp = [0]*13
        if s == "?":
            for i in range(13):
                for j in range(10):
                    dp[(10*i+j)%13] += prev[i]
        else:
            s = int(s)
            for i in range(13):
                dp[(10*i+s)%13] += prev[i]
        dp = [x % MOD for x in dp]
print(dp[5])

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

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

for s in S:
    prev = [x for x in dp]
    dp = [0]*13
    if s == "?":
        r = range(10)
    else:
        r = [int(s)]
    for i in range(13):
        for x in r:
            dp[(10*i+x)%13] += prev[i]
    dp = [x % MOD for x in dp]
print(dp[5])

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

dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1
for i in range(l):
    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):

number=input()
length=len(number)



sizemin=1000000007


dp=[[0 for i in range(13)] for j in range(length)]


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


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


        

for n in range(length-1):
    

    
    checknum=number[-1*(n+1)-1]


    
    if checknum!="?":
        
        
        for m in range(13):
            dp[n+1][(m+modlist[int(checknum)])%13]=dp[n][m]

        
        
        
        
        
    
    else:
    
    
        for checknum in range(10):
            for m in range(13):
                dp[n+1][(m+modlist[int(checknum)])%13]=(dp[n+1][(m+modlist[int(checknum)])%13]+dp[n][m])%sizemin


    
    modlist=[(j*10)%13 for j in modlist]


print(dp[-1][5])

Solution (Python):
x = 1000000007

S = input()
S = [int(s) if s != '?' else s for s in S]

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

for i, s in enumerate(S):
    for j in range(10):
        if s != '?' and s != j:
            continue

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

print(int(dp[-1][5] % x))

Solution (Python):
from bisect import bisect_left, bisect_right; from collections import Counter, defaultdict, deque, OrderedDict; from copy import deepcopy; from fractions import gcd; from functools import lru_cache, reduce; from math import ceil, floor; from sys import stdin, setrecursionlimit
import heapq as hq; import itertools as its; import operator as op



inf = float('inf')
MOD = 1000000007
input = stdin.readline


def main():
    s = get_str()
    dp = [[0] * 13 for _ in range(len(s) + 1)]
    dp[0][0] = 1
    for i, c in enumerate(s):
        ds = [int(c)] if c != '?' else range(10)
        for d in ds:
            for j in range(13):
                dp[i+1][(j * 10 + d) % 13] += dp[i][j]
                dp[i+1][(j * 10 + d) % 13] %= MOD
    print(dp[len(s)][5])
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def gets(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    setrecursionlimit(4100000)
    main()

Solution (Python):
MOD=1000000007
s = [int(x) if x!="?" else -1 for x in input()]
n=len(s)
count=0
dp=[[0 for j in range(13)] for i in range(n+1)]
dp[0][0]=1
for i in range(n):
  if count%50==0:
    for m in range(13):
      dp[i][m] =dp[i][m]%MOD
  
  for j in range(13):
    
    if s[i]==-1:
      count+=1
      for k in range(10):
        dp[i+1][(j*10+k)%13]+=dp[i][j]
        

    
    else:
      dp[i+1][(j*10+s[i])%13]+=dp[i][j]

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

Solution (Python):
MOD=1000000007
s = [int(x) if x!="?" else -1 for x in input()]
n=len(s)
count=0
dp=[[0 for j in range(13)] for i in range(n+1)]
dp[0][0]=1
for i in range(n):
  if count%50==0:
    for m in range(13):
      dp[i][m] =dp[i][m]%MOD
  
  for j in range(13):
    
    if s[i]==-1:
      count+=1
      for k in range(10):
        dp[i+1][(j*10+k)%13]+=dp[i][j]
        

    
    else:
      dp[i+1][(j*10+s[i])%13]+=dp[i][j]

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

Solution (Python):
s = input()
n = len(s)
MOD = 1e9 + 7
dp = [[0] * 13 for _ in range(n)]
for i in range(10):
	if s[0] == "?":
		dp[0][i] = 1
	else:
		cur = ord(s[0]) - ord("0")
		dp[0][cur] = 1
for i in range(1, n):
	if s[i] != "?":
		cur = ord(s[i]) - ord("0")
		for j in range(13):
			dp[i][(10 * j + cur) % 13] += dp[i - 1][j] % MOD
	else:
		for j in range(13):
			for cur in range(10):
				dp[i][(10 * j + cur) % 13] += dp[i - 1][j] % MOD

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

Solution (Python):
import itertools
S = input()[::-1]
mod = 10**9 + 7
A = [0] * 13
N = 0
for i, v in enumerate(S):
    p = pow(10, i, 13)
    if v == '?':
        A[p] += 1
    else:
        N += int(v) * p
        N %= 13
dp = [0] * 13
dp[N] = 1
for i, v in enumerate(A):
    for _ in range(v):
        dp_old = dp[:]
        for j, k in itertools.product(range(1, 10), range(13)):
            x = (j * i + k) % 13
            dp[x] += dp_old[k]
            dp[x] %= mod
print(dp[5])

Solution (Python):
S = input().strip()

MOD = 10 ** 9 + 7

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

for _i, s in enumerate(S):
    i = _i + 1

    if s == '?':
        candidate = range(10)
    else:
        candidate = [int(s)]

    for j in range(13):
        for c in candidate:
            m = (j * 10 + c) % 13
            DP[i][m] += DP[i-1][j]
    for j in range(13):
        DP[i][j] %= MOD

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

Solution (Python):
from collections import defaultdict
S = str(input())
N = len(S)
mod = 10 ** 9 + 7

dp = [[0 for _ in range(13)] for _ in range(N)]
if S[0] == '?':
    for j in range(10):
        dp[0][j] = 1
else:
    dp[0][int(S[0])] = 1

residualDict = defaultdict(list)
for s in range(0, 10):
    for j in range(0, 13):
        for k in range(0, 13):
            if (10 * k + s) % 13 == j:
                residualDict[s].append([j, k])

for i in range(1, N):
    if S[i] == '?':
        for s in range(0, 10):
            tmpList = residualDict[s]
            for j, k in tmpList:
                dp[i][j] += dp[i - 1][k]
    else:
        s = int(S[i])
        tmpList = residualDict[s]
        for j, k in tmpList:
            dp[i][j] += dp[i-1][k]

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

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

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

text=input()
lst=list(text)
lst.reverse()
digit=len(lst)




six=[[0,0],[0,0],[0,0],[0,0],[0,0],[0,0]]
for i in range(digit):
  if(lst[i]=="?"):
    six[i%6][1]=six[i%6][1]+1
  else:
    six[i%6][0]=(six[i%6][0]+int(lst[i]))%13

    

rem=-(six[0][0]-3*six[1][0]-4*six[2][0]
      -1*six[3][0]+3*six[4][0]+4*six[5][0]-5)%13


def mat1(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i-1)%13]+ls[(i-2)%13]
               +ls[(i-3)%13]+ls[(i-4)%13]+ls[(i-5)%13]
               +ls[(i-6)%13]+ls[(i-7)%13]+ls[(i-8)%13]
               +ls[(i-9)%13])%M
  return val_ls
def mat10(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i+3)%13]+ls[(i+6)%13]
               +ls[(i+9)%13]+ls[(i+12)%13]+ls[(i+15)%13]
               +ls[(i+18)%13]+ls[(i+21)%13]+ls[(i+24)%13]
               +ls[(i+27)%13])%M
  return val_ls
def mat100(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i+4)%13]+ls[(i+8)%13]
               +ls[(i+12)%13]+ls[(i+16)%13]+ls[(i+20)%13]
               +ls[(i+24)%13]+ls[(i+28)%13]+ls[(i+32)%13]
               +ls[(i+36)%13])%M
  return val_ls
def mat1000(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i+1)%13]+ls[(i+2)%13]
               +ls[(i+3)%13]+ls[(i+4)%13]+ls[(i+5)%13]
               +ls[(i+6)%13]+ls[(i+7)%13]+ls[(i+8)%13]
               +ls[(i+9)%13])%M
  return val_ls
def mat10000(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i-3)%13]+ls[(i-6)%13]
               +ls[(i-9)%13]+ls[(i-12)%13]+ls[(i-15)%13]
               +ls[(i-18)%13]+ls[(i-21)%13]+ls[(i-24)%13]
               +ls[(i-27)%13])%M
  return val_ls
def mat100000(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i-4)%13]+ls[(i-8)%13]
               +ls[(i-12)%13]+ls[(i-16)%13]+ls[(i-20)%13]
               +ls[(i-24)%13]+ls[(i-28)%13]+ls[(i-32)%13]
               +ls[(i-36)%13])%M
  return val_ls



modulos=[1,0,0,0,0,0,0,0,0,0,0,0,0]
for j in range(six[0][1]):
  modulos=mat1(modulos)
for j in range(six[1][1]):
  modulos=mat10(modulos)
for j in range(six[2][1]):
  modulos=mat100(modulos)
for j in range(six[3][1]):
  modulos=mat1000(modulos)
for j in range(six[4][1]):
  modulos=mat10000(modulos)
for j in range(six[5][1]):
  modulos=mat100000(modulos)
print(modulos[rem])

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

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

S = input()
N = len(S)

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

for i, s in enumerate(S):
    c = -1 if s == "?" else int(s)

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

    for r in range(13):
        dp[i + 1][r] = dp[i + 1][r] % MOD

print(dp[N][5])

Solution (Python):
import math
MOD = 10**9+7
s = [int(x) if x!="?" else -1 for x in input()]
n =len(s)
A=13
data=[4,3,12,9,10,1]*math.ceil(n/6)
data=data[-n:]

dp=[[0 for i in range(A+1)] for j in range(n+1)]
dp[0][0]=1

def benri(a,i,j):
	if j-a*data[i]%A>=0:
		re = j-a*data[i]%A
	else:
		re = j-a*data[i]%A+13
	return re

for i in range(n):
	for j in range(A+1):
		if s[i]!=-1:
			dp[i+1][j]=dp[i][benri(s[i],i,j)]%MOD

		else:
			for c in range(10):
				dp[i+1][j]+=dp[i][benri(c,i,j)]%MOD

			
			

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

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

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

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

S=input()

dp=[]
for i in range(len(S)):
  dp.append([0]*13)


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

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

Solution (Python):
mod = 10**9+7
S = [int(x) if x != "?" else -1 for x in input()]

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

for i in range(len(S)):
    if S[i] == -1:
        for d in range(10):
            for j in range(13):
                dp[i+1][(j*10+d) % 13] += dp[i][j]
    else:
        d = S[i]
        for j in range(13):
            dp[i+1][(j*10+d) % 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):
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
N = len(s)
if s[-1]=="?":
    dp = [1]*13
    dp[10:13] = [0,0,0]
else:
    dp = [0]*13
    dp[int(s[-1])] = 1
if N==1:
    print(dp[5])
    exit()
else:
    mul = 10
    for i in reversed(range(N-1)):
        nextdp = [0] * 13
        if s[i]=="?":
            for j in range(10):
                for k in range(13):
                    l = (j*mul+k) % 13
                    nextdp[l] += dp[k]
                    nextdp[l] %= mod
        else:
            for k in range(13):
                l = (int(s[i])*mul+k) % 13
                nextdp[l] += dp[k]
                nextdp[l] %= mod
        mul *= 10
        mul %= 13
        dp = nextdp
    print(dp[5])
    exit()

Solution (Python):
MOD = 1000000007;

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

n=len(s)

r=[0]*13

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

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

Solution (Python):

import copy
import random
import bisect 
import fractions 
import math
import sys
import bisect

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

def LI(): return list(map(int, sys.stdin.readline().split()))

S = list(str(input()))
S.reverse()
extra = 0
each_extras = [[] for i in range(S.count("?"))]
cnt = 0
mul = 1
for i in range(len(S)):
    if S[i] == "?":
        each_extras[cnt] = []
        for x in range(10):
            each_extras[cnt].append(x * mul % 13)
        cnt += 1
    else:
        extra += int(S[i]) * mul % 13
        extra %= 13

    mul = mul * 10 % 13




dp = [[0 for i in range(13)] for j in range(cnt+1)]
dp[0][extra % 13] = 1
for i in range(cnt):
    for extras in each_extras[i]:
        for j in range(13):
            dp[i+1][(extras + j)%13] += dp[i][j]
            dp[i+1][(extras + j)%13] %= mod


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

"""
S = list(str(input()))

dp = [[0 for i in range(13)]for j in range(len(S)+1)]
dp[0][0] = 1
S.reverse()
mul = 1
for i in range(len(S)):
    if S[i] == "?":
        for j in range(10):
            for k in range(13):
                dp[i+1][(mul*j+k)%13] += dp[i][k]
                dp[i+1][(mul*j+k)%13] %= mod
    else:
        for k in range(13):
            dp[i+1][(int(S[i])*mul+k)%13] += dp[i][k]
            dp[i+1][(int(S[i])*mul+k)%13] %= mod
    mul *= 10
    mul %= 13


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

Solution (Python):

import copy
import random
import bisect 
import fractions 
import math
import sys
import bisect

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

def LI(): return list(map(int, sys.stdin.readline().split()))


"""
S.reverse()
extra = 0
each_extras = [[0 for i in range(10)] for i in range(S.count("?"))]
cnt = 0
for i in range(len(S)):
    if S[i] != "?":
        extra += int(S[i]) * 10 ** i
    else:
        each_extras[cnt] = []
        for x in range(10):
            each_extras[cnt].append(x * 10 ** i % 13)
            
        cnt += 1




dp = [[0 for i in range(13)] for j in range(cnt+1)]
dp[0][extra % 13] = 1
for i in range(cnt):
    for extras in each_extras[i]:
        for j in range(13):
            dp[i+1][(extras + j)%13] += dp[i][j]
            dp[i+1][(extras + j)%13] %= mod
    for j in range(13):
        dp[i+1][j] = dp[i+1][j] % mod



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


S = list(str(input()))

dp = [[0 for i in range(13)]for j in range(len(S)+1)]
dp[0][0] = 1
S.reverse()
mul = 1
for i in range(len(S)):
    if S[i] == "?":
        for j in range(10):
            for k in range(13):
                dp[i+1][(mul*j+k)%13] += dp[i][k]
                dp[i+1][(mul*j+k)%13] %= mod
    else:
        for k in range(13):
            dp[i+1][(int(S[i])*mul+k)%13] += dp[i][k]
            dp[i+1][(int(S[i])*mul+k)%13] %= mod
    mul *= 10
    mul %= 13


print(dp[-1][5])

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

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

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

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

dp = [[0 for j in range(13)] for i in range(len(S)+1)]
dp[0][0] = 1
for i in range(1, len(S)+1):
    s = S[i-1]

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

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

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

dp[0][0] = 1

for i in range(len(S)):  
    for remain in range(13):
        if S[i] == '?':
            for j in range(10):
                next_remain = (remain*10 + j) % 13
                
                dp[i+1][next_remain] += dp[i][remain]
                dp[i+1][next_remain] %= 1000000007
        else:
            next_remain = (remain*10 + int(S[i])) % 13
            
            dp[i+1][next_remain] += dp[i][remain]
            dp[i+1][next_remain] %= 1000000007

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

Solution (Python):
S = [int(x) if x != '?' else '?' for x in input()]
length = len(S)

A = [0] * 13
B = [0] * 13
mod = 5
first = 0
r = 1

for i in range(length):
    a = S[length - i- 1]
    if a != '?':
        a = (a * r) % 13
        mod -= a
        mod %= 13

    elif first == 0:
        for j in range(10):
            a = (j * r) % 13
            A[a] += 1
        first = 1

    else:
        for j in range(10):
            a = (j * r) % 13
            for k in range(13):
                B[(k + a) % 13] += A[k]
                B[(k + a) % 13] %= 10 ** 9 + 7
        A = B
        B = [0] * 13
    r = (r * 10) % 13

if first == 0 and mod == 0:
    print(1)
elif first == 0 and mod != 0:
    print(0)
else:
    print(A[mod])

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


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

S_length = len(S)
MOD = 1000000007
dp[0][0] = 1  


for i in range(1, S_length+1):
    for remain in range(13):  
        if S[i-1] == '?':  
            for j in range(10):
                next_remain = (remain*10+j) % 13  

                
                dp[i][next_remain] += dp[i-1][remain]
                dp[i][next_remain] %= MOD
        else:
            next_remain = (remain*10 + int(S[i-1])) % 13
            
            dp[i][next_remain] += dp[i-1][remain]
            dp[i][next_remain] %= MOD

print(dp[S_length][5])

Solution (Python):
S = input()
N = len(S)
sosu = 10 ** 9 + 7
dp = [[0 for i in range(13)] for j in range(N)]
j = 0
if S[j] == '?':
    flag = -1
else:
    flag = int(S[j])
if flag == -1:
    for i in range(10):
        dp[j][i] += 1
else:
    dp[j][flag] = 1

for j in range(1, N):
    if S[j] == '?':
        flag = -1
    else:
        flag = int(S[j])
    for k in range(10):
        if flag == -1:
            for i in range(13):
                dp[j][(i * 10 + k) % 13] += dp[j - 1][i]
            for i in range(13):
                dp[j][i] = dp[j][i] % sosu
        else:
            for i in range(13):
                dp[j][(i * 10 + flag) % 13] = dp[j-1][i]
 
print(dp[N-1][5])

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

ans_old = [0] * 13
ans_old[0] = 1
for s in S:
    ans = [0] * 13
    if s == "?":
        for i in range(10):
            for j in range(13):
                ans[(j*10 + i)%13] = (ans[(j*10 + i)%13] + ans_old[j]) % mod 
    else:
        i = int(s)
        for j in range(13):
            ans[(j*10 + i)%13] = (ans[(j*10 + i)%13] + ans_old[j]) % mod 
    ans_old = ans

print(ans[5])

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] == '?':
        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

print(dp[n][5])

Solution (Python):
mod = 10 ** 9 + 7
s = input()
n = len(s)
dp = [[0 for _ in range(13)] for _ in range(n + 1)]
dp[0][0]=1
for i in range(n):
    if s[i] == '?': 
        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):
S = input()

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

for i in range(N):
    s = S[i]
    for j in range(10):
        if s != "?" and s != str(j):
            continue
        for r in range(13):
            dp[i+1][(r * 10 + j) % 13] += dp[i][r]
    for j in range(13):
        dp[i+1][j] %= mod

print(dp[N][5])

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

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

for c in s[::-1]:
  
  nextDP = [0] * 13
  if c == "?":
    for k in range(10):
      for j in range(13):
        nextDP[(k * mul + j)%13] += dp[j]
        nextDP[(k * mul + j)%13] %= mod
      
  else:
    k = int(c)
    for j in range(13):
        nextDP[(k * mul + j)%13] += dp[j]
        nextDP[(k * mul + j)%13] %= mod

  mul *= 10
  mul %= 13
  dp = nextDP

print(dp[5])

Solution (Python):
def main():
    MOD=10**9+7
    s="0"+input()
    dp=[[0]*len(s)for i in range(13)]
    dp[0][0]=1
    for k,j in enumerate(s[1:]):
        for i in range(13):
            if dp[i][k]:
                if j=="?":
                    for r in range(10):
                        dp[(10*i+r)%13][k+1]+=dp[i][k]%MOD
                else:
                    dp[int(str(i)+j)%13][k+1]+=dp[i][k]%MOD
    print(dp[5][-1]%MOD)
if __name__ == '__main__':
    main()

Solution (Python):
from itertools import product

S = input()
N = len(S)

l = [0 for i in range(13)]
l[0] = 1

x = 1
mod = 10**9 + 7

for i in range(N):
    tmp = [0 for i in range(13)]
    if S[-i-1] == '?':
        for i,j in product(range(13), range(10)):
            tmp[(i + x*j) % 13] += l[i] % mod
    else:
        num = int(S[-i-1])
        for i in range(13):
            tmp[(i + x*num) % 13] += l[i] % mod
    l = tmp
    x = 10 * x % 13

print(l[5] % mod)

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

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

print(dp[-1][5])

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