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


table = {}
pairs = [[((i*10 + j)%13, i) for i in range(13)] for j in range(13)]
mod = 10**9 + 7
for i in range(13):
    table[i] = tuple((i + j*13)//10 for j in range(10))

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

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

for i in range(1, len(S)):
    s = S[i]
    if s == "?":
        for j in range(13):
            for k in table[j]:
                dp[i][j] += dp[i-1][k] % mod
    else:
        s = int(s)
        for pair in pairs[s]:
            dp[i][pair[0]] = dp[i-1][pair[1]] % mod

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

Solution (Python):
S = input()


table = {}
pairs = [[((i*10 + j)%13, i) for i in range(13)] for j in range(13)]
mod = 10**9 + 7
for i in range(13):
    table[i] = tuple((i + j*13)//10 for j in range(10))

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

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

for i in range(1, len(S)):
    s = S[i]
    if s == "?":
        for j in range(13):
            for k in table[j]:
                dp[i][j] += dp[i-1][k]
            dp[i][j] %= mod
    else:
        s = int(s)
        for pair in pairs[s]:
            dp[i][pair[0]] = dp[i-1][pair[1]] % mod

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

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

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

S = input()

dp = [[0] * 13 for _ in range(len(S) + 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 k in range(13):
            dp[i + 1][(k * 10 + j) % 13] += dp[i][k]
    for j in range(13):
        dp[i + 1][j] %= mod

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

Solution (Python):
MOD = 1000000007
s = str(input())
n = len(s)
dp = [[0 for i in range(13)] for j in range(n + 1)]

dp[0][0] = 1
for i in range(n):
    c = -1 if s[i] == "?" else 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):
M=10**9+7
r=tuple(tuple((j-k)*9%13for j in range(10))for k in range(13))
d=[1]+[0]*12
for c in input():
    if c>'9':
        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):
def main():
  M=10**9+7
  r=tuple(tuple((j-k)*9%13for j in range(10))for k in range(13))
  d=[1]+[0]*12
  for c in input():
    if c>'9':
      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])
main()

Solution (Python):
import sys
input = sys.stdin.readline
def main():  
    S = list(input())
    S.pop()
    length=len(S)
    dp = [0]*13
    dp[0]=1
    mul=1
    mod=1000000007
    for i in range(1,length+1):
        next_dp = [0]*13
        for j in range(13):
            if S[length-i] == "?":
                for k in range(10):
                    j_sub=(j+k*mul)%13
                    next_dp[j_sub]+=dp[j]
                    next_dp[j_sub]%=mod
            else:
                j_sub=(j+int(S[length-i])*mul)%13
                next_dp[j_sub]+=dp[j]
                next_dp[j_sub]%=mod
        dp=next_dp
        mul=mul*10%13
    print(dp[5]%1000000007)
if __name__ == "__main__":
    main()

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

for k in range(LS):
    
    
    s = S[k]
    if s == '?':
        add = range(10)
    else:
        add = [int(s)]
    for i in range(13):
        for a in add:
            dp[k+1][(i*10+a)%13] += dp[k][i]
    dp[k+1] = [x % MOD for x in dp[k+1]]
print(dp[LS][5])

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

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

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

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

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

dp=[(i,0) for i in range(13)]
dp=dict(dp)
dp[0]=1

i=0
mul=1

for k in reversed(S):
    newdp=dict([(i,0) for i in range(13)])
    if k==-1:
        for s in range(10):
            for j in range(13):               
                newdp[(mul*s + j) % 13] += dp[j]%(10**9+7)
    else:
        for j in range(13):
            newdp[(mul*k + j) % 13] += dp[j]%(10**9+7)
    dp=newdp
    mul = (mul *10)%13


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

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

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

i=0
for k in S:
    if k==-1:
        for s in range(10):
            for j in range(13):
                dp[i + 1][(s + j*10) % 13] += dp[i][j]%(10**9+7)

    else:
        k=int(k)
        for j in range(13):
            dp[i + 1][(j *10 + k) % 13] += dp[i][j]%(10**9+7)
        
    i += 1


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

Solution (Python):


MOD = int(1e9)+7

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

n = len(S)

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

dp[0][0] = 1


for i in range(n):
    c = S[i]
    if c == -1:
        for j in range(10):
            for ki in range(13):
                dp[i + 1][(ki * 10 + j) % 13] += dp[i][ki]
    else:
        for ki in range(13):
            dp[i + 1][(ki * 10 + c) % 13] += dp[i][ki]        
    for j in range(13):
        dp[i+1][j] %= MOD



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

Solution (Python):

N=input()

lists = []
temp=[i for i in range(10)]

MOD=10**9+7

dic={0:1}

for i in N:
    new_dic={}
    hoge=list(dic.items())
    if i == "?":
        for amari,count in hoge:
            amari*=10
            for num in temp:
                a = (amari + num) % 13
                if a in new_dic:
                    new_dic[a]+=count
                else:
                    new_dic[a]=count
    else:
        num=int(i)
        for amari,count in hoge:
            a = (amari*10 + num)%13
            if a in new_dic:
                new_dic[a]+=count
            else:
                new_dic[a]=count
    for key in new_dic:
        new_dic[key] %= MOD
    dic = new_dic

try:
    print(dic[5])
except:
    print(0)

Solution (Python):
S = input()

mod = 10 ** 9 + 7
dp = [[0 for _ in range(13)] for _ in range(len(S))]
if S[0] == "?":
  for i in range(10):
    dp[0][i] = 1
else:
  dp[0][int(S[0])] = 1

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

print(dp[len(S) - 1][5] % (10 ** 9 + 7))

Solution (Python):
MOD = 10**9+7
s = input()
sl = list(s)
n=len(s)
dsl={i:sl[i] for i in range(n)}

dp={i:[0]*13 for i in range(n+1)}

dp[0][0]=1
for i in range(n):
    for k in range(10):
        if dsl[i] != "?" and dsl[i] != str(k):
            continue
        for j in range(13):
            dp[i+1][(j*10+k)%13] += dp[i][j]%MOD

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

Solution (Python):
MOD = 10**9+7
s = input()
ind = list(range(len(s)))
sl = list(s)

dsl = dict(zip(ind, sl))


ind2 = list(range(13))
dp={}

for i in range(len(s)+1):
    
    dp.setdefault(i, dict(zip(ind2,[0]*13)))



dp[0][0]=1

for i in range(len(s)):
    for k in range(10):
        if dsl[i] != "?" and dsl[i] != str(k):
            continue
        for j in range(13):
            dp[i+1][(j*10+k)%13] += dp[i][j]%MOD
    
    


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

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

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

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

for i in range(2, lenS+1):
    chara = S[i-1]
    if chara=='?':
        for d in range(13):
            for e in range(10):
                newd = (d*10+e)%13
                dp[i][newd] = (dp[i][newd]+dp[i-1][d])%div
    else:
        for d in range(13):
            newd = (d*10+int(chara))%13
            dp[i][newd] = (dp[i][newd]+dp[i-1][d])%div

print(dp[-1][5])

Solution (Python):

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]=="?":
		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]%=(10**9+7)
print(dp[n][5]%(10**9+7))

Solution (Python):
S=input()
N=len(S)
dp=[[0 for i in range(13)] for j in range(N+1)]
q=[(i*10)%13 for i in range(13)]
r=[q.index(i) for i in range(13)]
MOD=10**9+7
if S[0]=="?":
  dp[1]=[1,1,1,1,1,1,1,1,1,1,0,0,0]
else:
  dp[1][int(S[0])]=1
for i in range(2,N+1):
  if S[i-1]=="?":
    for j in range(13):
      for x in range(10):
        dp[i][(x+q[j])%13]+=dp[i-1][j]
    dp[i]=[dp[i][j]%MOD for j in range(13)]
  else:
    for j in range(13):
      x=int(S[i-1])
      dp[i][(x+q[j])%13]=dp[i-1][j]
print(dp[N][5])

Solution (Python):
s = input()
s = s[::-1]
mod = 10 ** 9 + 7
table = [[0] * 13 for _ in range(len(s) + 2)]
table[0][0] = 1
dd = 1
for c in range(len(s)):
    if s[c] == "?":
        for n in range(10):
            for i in range(13):
                table[c + 1][(i + n * dd) % 13] += table[c][i]
                table[c + 1][(i + n * dd) % 13] %= mod
    else:
        num = int(s[c])
        for i in range(13):
            table[c + 1][(i + num * dd) % 13] += table[c][i]
            table[c + 1][(i + num * dd) % 13] %= mod
    dd = (dd * 10) % 13
print(table[c + 1][5])

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

dd = 1

for i in range(len(S)):
    if S[i] == '?':
        for j in range(13):
            for k in range(10):
                table[i+1][(j + dd * k)  % 13] += table[i][j]
                table[i+1][(j + dd * k)  % 13] %= mod
    else:
        num = int(S[i])
        for j in range(13):
            table[i+1][(j + dd * num)  % 13] += table[i][j]
            table[i+1][(j + dd * num)  % 13] %= mod

    dd = (dd * 10) % 13

print(table[i+1][5])

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

dd = 1

for i in range(N):
    if S[i] == '?':
        for k in range(10):
            for j in range(13):
                table[i+1][(j + dd * k)  % 13] += table[i][j]
                table[i+1][(j + dd * k)  % 13] %= mod
    else:
        num = int(S[i])
        for j in range(13):
            table[i+1][(j + dd * num)  % 13] += table[i][j]
            table[i+1][(j + dd * num)  % 13] %= mod

    dd = (dd * 10) % 13

print(table[N][5])

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

dd = 1

for i in range(N):
    if S[i] == '?':
        for j in range(13):
            for k in range(10):
                table[i+1][(j + dd * k)  % 13] += table[i][j]
                table[i+1][(j + dd * k)  % 13] %= mod
    else:
        num = int(S[i])
        for j in range(13):
            table[i+1][(j + dd * num)  % 13] += table[i][j]
            table[i+1][(j + dd * num)  % 13] %= mod

    dd = (dd * 10) % 13

print(table[N][5])

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

dd = 1

for i in range(N):
    c = S[i] != '?'
    for j in range(13):
        for k in range(10):
            if c and int(S[i]) != k:
                continue
            table[i+1][(j + dd * k)  % 13] += table[i][j]
            table[i+1][(j + dd * k)  % 13] %= mod
    dd = (dd * 10) % 13

print(table[N][5])

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

dd = 1

for i, char in enumerate(reversed(S)):
    c = char != '?'
    for j in range(13):
        for k in range(10):
            if c and int(char) != k:
                continue
            table[i+1][(j + dd * k)  % 13] += table[i][j]
            table[i+1][(j + dd * k)  % 13] %= mod
    dd = (dd * 10) % 13

print(table[N][5])

Solution (Python):
s = input()
s = s[::-1]
mod = 10 ** 9 + 7
table = [[0] * 13 for _ in range(len(s) + 2)]
table[0][0] = 1
dd = 1
for c in range(len(s)):
    if s[c] == "?":
        for n in range(10):
            for i in range(13):
                table[c + 1][(i + n * dd) % 13] += table[c][i]
                table[c + 1][(i + n * dd) % 13] %= mod
    else:
        num = int(s[c])
        for i in range(13):
            table[c + 1][(i + num * dd) % 13] += table[c][i]
            table[c + 1][(i + num * dd) % 13] %= mod
    dd = (dd * 10) % 13
print(table[c + 1][5])

Solution (Python):
from copy import deepcopy

S = input()

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

tens_mod = [1, 10, 9, 12, 3, 4]
mod = int(10**9 + 7)

for i, s in enumerate(S[::-1]):
    if s == "?":
        for j in range(13):
            dp[j] = 0
            for k in range(10):
                dp[j] += dp_past[(j - k * tens_mod[i % 6]) % 13]
            dp[j] %= mod

    else:
        k = int(s)
        for j in range(13):
            dp[j] = dp_past[(j - k * tens_mod[i % 6]) % 13]
    dp_past = deepcopy(dp)

print(dp[5] % mod)

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


def main():
    S = input().rstrip()
    DP = [0] * 13
    n = len(S)
    DP[0] = 1

    for i in range(0, n):
        preDP = DP
        DP = [0] * 13
        if S[i] == '?':
            for k in range(13):
                for x in range(10):
                    t = (x + 10*k) % 13
                    DP[t] += preDP[k]
                    DP[t] %= MOD
        else:
            y = int(S[i])
            for k in range(13):
                t = (y+10*k) % 13
                DP[t] += preDP[k]
                DP[t] %= MOD

    ans = DP[5]
    print(ans)


if __name__ == '__main__':
    main()

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

remainder = {0: 1}

for s in S:
    rx = {r: 0 for r in range(13)}
    for n in (range(10) if s == '?' else [int(s)]):
        for r in remainder:
            r2 = (r * 10 + n) % 13
            rx[r2] += remainder[r]
            rx[r2]  = rx[r2] % modulo
    remainder = rx

print(remainder[5] % modulo)

Solution (Python):

s = input()
n = len(s)
now = [1,0,0,0,0,0,0,0,0,0,0,0,0]
for i in range(n):
  last = now
  now = [0 for _ in range(13)]
  here = s[i]
  if here == '?':
    for k in range(10):
      for j in range(13):
        now[(10*j+k)%13] += last[j]
  else:
    k = int(here)
    for j in range(13):
      now[(10*j+k)%13] += last[j]
  for j in range(13):
    now[j] %= 10**9+7
print(now[5])

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


def main(s):
    reminder = [[(j - k) * 9 % 13 for j in range(10)] for k in range(13)]
    dp = [1] + [0] * 12
    for char in s:
        if char == "?":
            dp = [sum(dp[j] for j in k) % MOD for k in reminder]
        else:
            dp = [dp[(int(char) - k) * 9 % 13] for k in range(13)]

    return dp[5]


S = input()
print(main(S))

Solution (Python):

P_MOD = 1000000007


def solve(S):
    
    
    MODS = [1, 10, 9, 12, 3, 4]

    
    
    priv = [1] + [0] * 12
    
    s = S[::-1]
    for i in range(0, len(s)):
        cur = [0] * 13
        d = s[i]
        
        if d == '?':
            for j in range(13):
                for di in range(10):
                    m = di * MODS[i % 6]
                    cur[(j+m) % 13] += priv[j]
        else:
            m = int(d) * MODS[i % 6]
            for j in range(13):
                cur[(m+j) % 13] = priv[j]
        
        for j in range(13):
            priv[j] = cur[j] % P_MOD
    return cur[5]


if __name__ == '__main__':
    S = input()

    ans = solve(S)

    print(ans % P_MOD)

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

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

for i,s in enumerate(S):
    m = pow(10,(N-i-1),13)
    if s == '?':
        for d in range(10):
            for k in range(13):
                dp[i+1][(k+m*d)%13] += dp[i][k]
    else:
        d = int(s)
        for k in range(13):
            dp[i+1][(k+m*d)%13] += dp[i][k]

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


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

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

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

print(dp[5])

Solution (Python):
S = [int(x) if x != "?" else -1 for x in input()]
mod = int(1e9+7)
r = [0]*13
if S[0] != -1:
    r[S[0]] = 1
else:
    for i in range(10):
        r[i] = 1
for i in range(1, len(S)):
    dp = [0] * 26
    for j in range(13):
        dp[j * 10 % 13] += (r[j] % mod)

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

Solution (Python):

S=list(input().strip())
S=[0]+S
l=len(S)
mod=10**9+7

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

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

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

Solution (Python):
N = input()[::-1]
iv = 1
MOD = 10**9+7
dp = [0]*13
dp[0]=1
ls = [0]*13
for i in range(len(N)):
  x = N[i]
  
  if x=='?':
    for j in range(13):
      for h in range(10):
        ls[(h*iv+j)%13] += dp[j]
        
  else:
    x = int(x)
    for j in range(13):
      ls[(j+x*iv)%13]+=dp[j]
      
  for j in range(13):
    dp[j] = (ls[j]%MOD)
    ls[j]=0
  iv *= 10
  iv %= 13
print(dp[5])

Solution (Python):
N = input()[::-1]
iv = 1
MOD = 10**9+7
dp = [0]*13
dp[0]=1
ls = [0]*13
for i in range(len(N)):
  x = N[i]
  
  if x=='?':
    for j in range(13):
      for h in range(10):
        ls[(h*iv+j)%13] += dp[j]
        
  else:
    x = int(x)
    for j in range(13):
      ls[(j+x*iv)%13]+=dp[j]
      
  for j in range(13):
    dp[j] = (ls[j]%MOD)
  ls = [0]*13
  iv *= 10
  iv %= 13
print(dp[5])

Solution (Python):
N = input()[::-1]
iv = 1
MOD = 10**9+7
dp = [0 for i in range(13)]
dp[0]=1
ls = [0 for i in range(13)]
for i in range(len(N)):
  x = N[i]
  if x=='?':
    for j in range(13):
      for h in range(10):
        ls[(h*iv+j)%13] += dp[j]
    for j in range(13):
      dp[j] = (ls[j]%MOD)
      ls[j] = 0
  else:
    x = int(x)
    for j in range(13):
      ls[(j+x*iv)%13]+=dp[j]
    for j in range(13):
      dp[j] = (ls[j]%MOD)
      ls[j]=0
  iv *= 10
  iv %= 13
print(dp[5])

Solution (Python):
import numpy as np
import sys
def input():
    return sys.stdin.readline()[:-1]












































MOD = 1000000007;

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):
N = input()[::-1]
iv = 1
MOD = 10**9+7
pdp = [0 for i in range(13)]
pdp[0]=1
dp = [0 for i in range(13)]
for i in range(len(N)):
  x = N[i]
  if x=='?':
    for j in range(13):
      for h in range(10):
        dp[(h*iv+j)%13] += pdp[j]
    for j in range(13):
      pdp[j] = (dp[j]%MOD)
      dp[j] = 0
  else:
    x = int(x)
    for j in range(13):
      dp[(j+x*iv)%13]+=pdp[j]
    for j in range(13):
      pdp[j] = (dp[j]%MOD)
      dp[j]=0
  iv *= 10
  iv %= 13
print(pdp[5])

Solution (Python):
from sys import stdin
S = (stdin.readline().rstrip())
dp = [[0]*13 for i in range(len(S)+1)]
MOD = 10**9+7
 
S = list(reversed(S))
dp[0][0] = 1
 
t = 1
for i, c in enumerate(S, 1):
    for j in range(13):
        if c == "?":
            for k in range(10):
                nj = (k*t+j) % 13
                dp[i][nj] = dp[i][nj] + dp[i-1][j]
                dp[i][nj] %= MOD
        else:
            nj = (int(c)*t+j) % 13
            dp[i][nj] = dp[i][nj] + dp[i-1][j]
            dp[i][nj] %= MOD
    t = (t*10)%13
print(dp[-1][5])

Solution (Python):
import math, heapq
from operator import itemgetter as ig
from collections import defaultdict as dd

INF = float("inf")
MOD = int(1e9 + 7)

class heapque:
    def __init__(self, *args):
        self.que = []
        for arg in args:
            self.push(arg)
    def push(self, v):
        heapq.heappush(self.que, v)
    def pop(self):
        return heapq.heappop(self.que)

def gcd(v1, v2):
    if v2 == 0:
        return v1
    return gcd(v2, v1 % v2)
def lcm(v1, v2):
    return (v1 // gcd(v1, v2)) * v2

def bsr(a, v, lo=0, hi=None):
    if hi == None:
        hi = len(a) - 1
    if hi < lo:
        return lo
    mi = (lo + hi) // 2
    if v < a[mi]:
        return bsr(a, v, lo, mi - 1)
    else:
        return bsr(a, v, mi + 1, hi)

class uft:
    def __init__(self, n):
        self.height = [1] * n
        self.group = [-1] * n
    def root(self, v):
        if self.group[v] < 0:
            return v
        self.group[v] = self.root(self.group[v])
        return self.group[v]
    def size(self, v):
        return - self.group[self.root(v)]
    def merge(self, v1, v2):
        v1, v2 = self.root(v1), self.root(v2)
        if v1 == v2:
            return
        if self.height[v1] < self.height[v2]:
            self.group[v2] += self.group[v1]
            self.group[v1] = v2
            self.height[v2] = max(self.height[v1] + 1, self.height[v2])
        else:
            self.group[v1] += self.group[v2]
            self.group[v2] = v1
            self.height[v1] = max(self.height[v1] , self.height[v2] + 1)

def main():
    S = input()
    dp = [[0 for _ in range(13)] for _ in range(len(S) + 1)]
    dp[0][0] = 1
    for i, s in enumerate(S):
        i += 1
        loop = range(10) if s == "?" else [int(s)]
        for n in range(13):
            for m in loop:
                dp[i][(n * 10 + m) % 13] += dp[i - 1][n]
                dp[i][(n * 10 + m) % 13] %= MOD
    print(dp[-1][5])

main()

Solution (Python):
MOD = 10**9+7
S=input()
dp_old=[0]*13
dp_new=[0]*13
dp_old[0]=1
for c in S:
    if c == '?':
        for i in range(10):
            for j in range(13):
                dp_new[(j*10+i)%13]+=dp_old[j]
    else:
        for i in range(13):
            dp_new[(i*10+int(c))%13]+=dp_old[i]
    dp_old = [i%MOD for i in dp_new]
    dp_new = [0]*13
print(dp_old[5])

Solution (Python):

S=raw_input()
l=len(S)

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

mod=10**9+7
keta=pow(10,l-1,13)

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

	keta=(keta*4)%13	

print dp[-1][5]

Solution (Python):
S=raw_input()
S=S[::-1]
l=len(S)

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

mod=10**9+7

dp2=[ 0 for _ in range(13) ]

keta=1

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

	dp=dp2
	keta=(keta*10)%13

print dp[5]

Solution (Python):
def main():
    M=10**9+7
    r=tuple(tuple((j-k)*9%13 for j in range(10))for k in range(13))
    d=[1]+[0]*12
    for c in input():
      if c>'9':
        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])
main()

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

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


dp[0][0] = 1

for i,s in enumerate(ss):
    if s == "?":
        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))%13] += dp[i][k] % MOD
            

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

Solution (Python):
def p_d():
    S = input()
    N = 13

    dp = [0] * N
    dp[0] = 1

    mul = 1
    mod = 10 ** 9 + 7

    for i in reversed(range(len(S))):
        nextDP = [0] * N
        c = S[i]
        if c == "?":
            for k in range(10):  
                for j in range(N):
                    nextDP[(k * mul + j) % N] += dp[j]
                    nextDP[(k * mul + j) % N] %= mod
        else:
            k = int(c)
            for j in range(N):
                nextDP[(k * mul + j) % N] += dp[j]
                nextDP[(k * mul + j) % N] %= mod
        mul *= 10
        mul %= N
        dp = nextDP

    print(int(dp[5]))


if __name__ == '__main__':
    p_d()

Solution (Python):
import itertools

def getint(): return int(input())
def getints(): return list(map(int, input().split()))

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):
    c = -1 if s[i] == '?' else ord(s[i]) - ord('0')
    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

res = dp[n][5]

print(res)

Solution (Python):
import numpy as np


def main():
    n = 13
    mod = 1000000007
    r = 5
    in_str = input()

    amari_l = amari_list(n)
    amari_m = amari_matrix(n, amari_l)

    ans_list = initial(in_str[-1:], n)

    for i, s in enumerate(reversed(in_str)):
        if i == 0:
            continue
        if s == "?":
            ans_list = np.dot(ans_list, amari_m[i % len(amari_m)]) % mod
        else:
            t = int(s) * amari_l[i % len(amari_l)] % n
            ans_list = np.roll(ans_list, t)

    print(int(ans_list[r] % mod))


def initial(s, n):
    if s == "?":
        return np.array([1 if i < 10 else 0 for i in range(n)], dtype='int64')
    else:
        return np.array([1 if i == int(s) else 0 for i in range(n)], dtype='int64')


def shift(n, r):
    return np.array([[1 if (i - j + r) % n == 0 else 0 for j in range(n)] for i in range(n)])


def amari_list(n):
    ret = []
    for i in range(n + 1):
        r = 10**i % n
        if r in ret:
            return ret
        else:
            ret.append(r)


def amari_matrix(n, amari_list):
    ret = np.zeros((len(amari_list), n, n))
    for i, j in enumerate(amari_list):
        tmp = np.zeros((n, n))
        for k in range(10):
            tmp += shift(n, j * k % n)
        ret[i] = tmp
    return ret


if __name__ == '__main__':
    main()

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

for i in range(len(S)):
    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[len(S)][5])

Solution (Python):
P=[1,10,9,12,3,4]
m=10**9+7
def f(A,p,N):
    if p==0:return [1&(i in N) for i in range(13)]
    p%=6
    B=[0]*13
    for n in N:
        for i in range(13):
            c=(i+(n*P[p]))%13
            B[c]=(B[c]+A[i])%m
    return B

S=reversed(input())
A=[0]
for p,s in enumerate(S):
    if s=="?":A=f(A,p,range(10))
    else:A=f(A,p,[int(s)])
print(A[5])

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 solve(string):
    n = len(string)
    q_pos = [i for i in range(n) if string[n - i - 1] == "?"]
    table = [[0] * 13 for _ in range(2)]
    table[0][int(string.replace("?", "0")) % 13] = 1
    for i in range(len(q_pos)):
        base = pow(10, q_pos[i], 13)
        for j in range(13):
            for k in range(10):
                table[1][(j + k * base) % 13] += table[0][j]
        for j in range(13):
            table[1][j] %= (10**9 + 7)
        table[0] = table[1]
        table[1] = [0] * 13
    return str(table[0][5])


if __name__ == '__main__':
    print(solve(input()))

Solution (Python):
S = list(input())
n = len(S)
dp = [[0] * 13 for _ in range(n + 1)]

MOD = 10 ** 9 + 7

def solve():
    res = 0
    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 k in range(13):
                dp[i + 1][(k * 10 + j) % 13] += dp[i][k]
        
        for j in range(13):
            dp[i + 1][j] %= MOD
    
    res = dp[n][5]
    return res

print (solve())