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):
M=10**9+7
r=[[(j-i)*4%13 for i in range(10)]for j in range(13)]
d=[1]+[0]*12
for c in input():
  if c>"9":
    d=[(sum(d[i] for i in j))%M for j in r]
  else:
    d=[d[((j-int(c))*4%13)] for j in range(13)]
    
print(d[5])

Solution (Python):
import sys
sys.setrecursionlimit(4100000)

import logging



logger = logging.getLogger(__name__)

import re


def resolve():
    S = sys.stdin.readline().split()[0]

    logger.debug(S)

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

    len_S = len(S)
    for i in range(1, len(S)):
        if S[i] == '?':
            for r in range(13):
                dp[i-1][r] %= (10**9 + 7)
                for j in range(10):
                    new_r =  j + r * 10
                    dp[i][new_r % 13] += dp[i-1][r]

        else:
            int_s = int(S[i])
            for r in range(13):
                new_r = int_s + r * 10
                dp[i][new_r % 13] += dp[i-1][r] % (10**9 + 7)

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

if __name__ == "__main__":
    resolve()





import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """??2??5"""
        output = """768"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """?44"""
        output = """1"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """7?4"""
        output = """0"""
        self.assertIO(input, output)
    def test_入力例_4(self):
        input = """?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76???"""
        output = """153716888"""
        self.assertIO(input, output)

Solution (Python):
import copy
S = input()
mod = 10 ** 9 + 7
N = 13
dp = [0] * N
dp[0] = 1

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

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

Solution (Python):


MOD = 1000000007


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


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]=="?":
    ks = list(range(10))
  else:
    ks = [int(S[i])]
  for j in range(13):
    for k in ks:
      dp[i][(j*10+k)%13] = (dp[i][(j*10+k)%13]+dp[i-1][j]) % MOD
print(dp[len(S)-1][5])

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

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

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

Solution (Python):
M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for c in reversed(input()):
    x, y = (0, p * 10) if c == '?' else (p * int(c), p * int(c) + 1)
    a = [sum(a[(i - j) % 13] for j in range(x, y, p)) % M for i in range(13)]
    p = p * 10 % 13
print(a[5])

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

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

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

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

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

Solution (Python):
s=input()
mod=10**9+7
dp = [[0]*15 for i in range(100005)]
dp[0][0]=1
for i in range(len(s)):
    keta = len(s)-i-1

    if s[i]=='?':
        nums = range(10)
    else:
        nums = [int(s[i])]
    
    tmp = pow(10,keta,13)
    for num in nums:
        amari = num*tmp%13
        for j in range(13):
            dp[i+1][(j+amari)%13]+=dp[i][j]
            dp[i+1][(j+amari)%13]%=mod

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

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

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

cur = [0] * 13
cur[0] = 1
r = 1
base = 0
for i in range(len(S)):
    s = S[-(i+1)]
    if s == '?':
        prev = cur
        cur = [sum(prev)] * 13
        for m in range(13):
            for d in range(10,13):
                cur[(m + r*d) % 13] -= prev[m]
        for m in range(13):
            cur[m] %= MOD
    else:
        base = (base + r*int(s)) % 13

    r = (10 * r) % 13

print(cur[(5-base) % 13])

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

Solution (Python):
inf = 10**9 + 7
s = input()
r = [[(j-k)*9%13 for j in range(10)] for k in range(13)]
d = [1] + [0]*12
for c in s:
    d = [sum(d[j] for j in k)%inf 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 = input()


num_mod = 10 ** 9 + 7
dp = [1] + [0]*12

for i in range(len(S)):
  nextdp = [0] * 13
  if S[i] == '?':
    for j in range(13):
      for k in range(10):
        nextdp[(j*10 + k)%13] += dp[j]
  else:
    for j in range(13):
      nextdp[(j*10 + int(S[i]))%13] += dp[j]
  for j in range(13):
    nextdp[j] %= num_mod
  dp = nextdp
  
print(dp[5])

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

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

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

mul = 10 
for order in range(1,len(s)):
    for j in range(13):
        if invs[order] == '?':
            for number in range(10):
                dp[order][ (j+number * mul )%13  ]  += dp[order-1][j]%MOD 
        else:
            number = int(invs[order])
            dp[order][(j+number * mul )%13 ]  += dp[order-1][j]%MOD
        dp[order][(j+number * mul )%13 ] %= MOD
    mul *= 10
    mul %= 13
print(dp[-1][5]%MOD)

Solution (Python):

S = input()
mod = 10**9+7
N = len(S)

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

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

print(dp[N][5])

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

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

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

mul = 10
for order in range(1,len(s)):
    for j in range(13):
        if invs[order] == '?':
            for number in range(10):
                dp[order][ (j+number * mul )%13  ]  += dp[order-1][j]%MOD
        else:
            number = int(invs[order])
            dp[order][(j+number * mul )%13 ]  += dp[order-1][j]%MOD
        dp[order][(j+number * mul )%13 ] %= MOD
    mul *= 10
    mul %= 13
print(dp[-1][5]%MOD)

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

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

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

print(dp[l][5])

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

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

S = input()
N = len(S)

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

for i, s in enumerate(S):
    if s == "?":
        c = -1
    else:
        c = 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] %= MOD

print(dp[N][5])

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

dp[N][0] = 1


mul = 1
for i in reversed(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][(j*mul+k)%13] += dp[i+1][k]
            dp[i][(j*mul+k)%13] %= mod
    mul *=10
    mul %=13


result = dp[0][5]

print(result)

Solution (Python):



def main():
    s = input()[::-1]
    mod = 10 ** 9 + 7

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

    
    digit = 1

    
    for si in s:
        
        next_dp = [0 for _ in range(n)]

        if si == '?':
            
            for q in range(10):
                
                
                
                for j in range(n):
                    next_dp[(q * digit + j) % n] += dp[j]
                    next_dp[(q * digit + j) % n] %= mod
        else:
            q = int(si)

            for j in range(n):
                next_dp[(q * digit + j) % n] += dp[j]
                next_dp[(q * digit + j) % n] %= mod

        
        dp = next_dp

        
        digit *= 10
        digit %= n

    
    print(dp[5])


if __name__ == '__main__':
    main()

Solution (Python):
M=10**9+7
r=[[(j-k)*9%13 for 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):
import numpy as np


def solve(s):
    MOD = 10 ** 9 + 7
    dp = np.zeros(13, dtype=np.int64)
    dp[0] = 1
    idx = np.zeros(13, dtype=np.int8)
    for i in range(13):
        idx[i * 10 % 13] = i
    window = np.ones(10, dtype=np.int8)
    for c in s:
        if c == '?':
            tdp = dp[idx]
            ndp = np.concatenate([tdp[4:], tdp])
            dp = np.convolve(ndp, window, mode='valid') % MOD
        else:
            dp = np.roll(dp[idx], int(c))
    return dp[5]


s = input()
print(solve(s))

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


S = input().rstrip()

MOD = 10 ** 9 + 7
n = len(S)



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

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
        
        
    res = dp[n][5]
    
print(res)

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

mod = 10**9 + 7

N = 13
dp = [0]*N
dp[0] = 1
mul = 1
for i in range(len(s)-1, -1, -1):
    nextDP = [0]*N
    if s[i] == '?':
        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(s[i])
        for j in range(N):
            nextDP[(k*mul + j)%N] += dp[j]
            nextDP[(k*mul + j)%N] %= mod

    mul = (mul*10)%N
    dp = nextDP

print(dp[5])

Solution (Python):
S = input()

mod = 10**9+7
N = len(S)

s = S[-1]
dp = [0]*13
if s=="?":
    dp[:10] = [1]*10
else:
    dp[int(s)] = 1

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

Solution (Python):

import sys

MOD = 1000000007  

def solve(S: str):
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(len(S))]
    if S[N-1] != '?':
        dp[0][int(S[N-1])] = 1
    else:
        dp[0] = [1,1,1,1,1,1,1,1,1,1,0,0,0]
    ten = [1]
    for i in range(1, len(S)):
        ten.append(ten[-1] * 10 % 13)
        ii = len(S) - i - 1
        for j in range(13):
            if S[ii] == '?':
                for ll in range(10):
                    kk = ll * ten[i] % 13
                    dp[i][j] += dp[i-1][(13 + j - kk)%13]
                    dp[i][j] %= MOD
            else:
                x = int(S[ii])
                m = x * ten[i] % 13
                dp[i][j] = dp[i-1][(13+j-m)%13]
                dp[i][j] %= MOD
    print(dp[len(S)-1][5])
    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):
def main():
    S = list(input())

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

main()

Solution (Python):
S = input()

mod = 10**9+7
N = len(S)
ans = 0

memo = {}
for i in range(1000):
    s = str(i).zfill(3)
    memo[s] = [0 for _ in [0]*13]
    memo[s][i%13] = 1

def rep_Q_count(s):
    memo[s] = [0 for _ in [0]*13]
    for q in range(10):
        s2 = s.replace("?",str(q),1)
        for i,n in enumerate(memo[s2]):
            memo[s][i] += n

for i in range(100):
    s = str(i).zfill(2)
    rep_Q_count(s+"?")
    rep_Q_count(s[0]+"?"+s[1])
    rep_Q_count("?"+s)
for i in range(10):
    s = str(i)
    rep_Q_count(s+"??")
    rep_Q_count("?"+s+"?")
    rep_Q_count("??"+s)
rep_Q_count("???")

s0 = S[max(0,N-3):N].zfill(3)
dp = memo[s0][:]
for i in range(1,(N-1)//3+1):
    s = S[max(0,N-(i+1)*3):N-i*3].zfill(3)
    j = i%2
    tmp = memo[s]
    dp2 = [0]*13
    for k,n in enumerate(tmp):
        for l,m in enumerate(dp):
            dp2[(l+k*((-1)**j))%13] += n*m
    dp = dp2
    for i in range(13):
        dp[i] %= mod
print(dp[5])

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

cur = [0] * 13
cur[0] = 1
r = 1
for i in range(len(S)):
    s = S[-(i+1)]
    if s == '?':
        digits = range(10)
    else:
        digits = [int(s)]

    prev = cur
    cur = [0] * 13
    for m in range(13):
        for d in digits:
            cur[(m + r*d) % 13] += prev[m]
    for m in range(13):
        cur[m] %= MOD
    r = (10 * r) % 13

print(cur[5])

Solution (Python):
S = input()

N = 13

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



mod = 10**9 + 7

mul = 1
for i in range(len(S))[::-1]:
    
    nextDP = [0] * N
    if S[i] == '?':
        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(S[i])
        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(dp[5])

Solution (Python):










BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001


S = input().strip()

N = 13

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

mul = 1
reversed_S = S[::-1]
for c in reversed_S:
    nextDP = [0]*N
    if c == '?':
        
        
        for k in range(10):
            for j in range(N):
                nextDP[(mul*k+j)%N] += dp[j]
                nextDP[(mul*k+j)%N] %= MOD
    else:
        k = int(c)
        for j in range(N):
            nextDP[(mul*k+j)%N] += dp[j]
            nextDP[(mul*k+j)%N] %= MOD

    mul *= 10
    mul %= N
    dp = nextDP[:]
print(dp[5])

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


def main():
    S = input()

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

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

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

        for j, v in enumerate(dp[i + 1]):
            dp[i + 1][j] = v % MOD

    print(dp[-1][5])


if __name__ == '__main__':
    main()

Solution (Python):

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

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

    for i, sk in enumerate(S):
        if i == 0:
            if sk == '?':
                for j in range(10):
                    dp[0][j] = 1
            else:
                s = int(sk)
                dp[0][s] = 1
            continue
        if sk == '?':
            for j in range(13):
                for l in range(10): 
                    k = (10*j+l)%13
                    dp[i][k] += dp[i-1][j]
        else:
            s = int(sk)
            for j in range(13):
                k = (10*j+s)%13
                dp[i][k] += dp[i-1][j]
        for j in range(13):
            dp[i][j] = dp[i][j] % 1000000007

    print(dp[-1][5])

if __name__ == '__main__':
    main()

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

MOD = 10 ** 9 + 7
S = input().rstrip()

ten = np.zeros(13, dtype=np.uint64)
ten[:10] += 1
add_all = [ten]
for _ in range(5):
  add_all.append(add_all[-1][np.arange(0,52,4)%13])

add_single = [[x * 10 ** i for x in range(10)] for i in range(6)]

add_all_count = [0] * 6
constant_term = 0
for i,s in enumerate(S[::-1]):
  if s == '?':
    add_all_count[i%6] += 1
  else:
    constant_term += add_single[i%6][int(s)]

def convolve(x,y):
  z = np.convolve(x,y) % MOD
  z[:12] += z[13:25]
  return z[:13] % MOD

def nth_convolve(arr,n):
  if n == 1:
    return arr
  x = nth_convolve(arr,n>>1)
  x = convolve(x,x)
  return convolve(arr,x) if n & 1 else x

dp = np.zeros(13, dtype=np.uint64)
dp[constant_term % 13] = 1
for arr,n in zip(add_all, add_all_count):
  if n > 0:
    dp = convolve(dp, nth_convolve(arr,n))

print(dp[5])

Solution (Python):

inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True 
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)


rem = [1,10,9,12,3,4]
s = input().strip()
sr = s[::-1]
n = len(s)
dp = [ [0]*13 for i in range(n) ]
if sr[0]=='?':
    for j in range(10):
        dp[0][j] = 1
else:
    j = int(sr[0])
    dp[0][j] = 1

for i in range(1,n):
    r = rem[i%6]
    if sr[i]=='?':
        for j in range(10):
            for k in range(13):
                dp[i][(k+j*r)%13] = (dp[i][(k+j*r)%13] + dp[i-1][k])%R
    else:
        j = int(sr[i])
        for k in range(13):
                dp[i][(k+j*r)%13] = (dp[i][(k+j*r)%13] + dp[i-1][k])%R

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

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

MOD = 10 ** 9 + 7
S = input().rstrip()

ten = np.zeros(13, dtype=np.int64)
ten[:10] += 1
add_all = [ten]
for _ in range(5):
  add_all.append(add_all[-1][np.arange(0,52,4)%13])

add_single = [[x * 10 ** i for x in range(10)] for i in range(6)]

add_all_count = [0,0,0,0,0,0]
constant_term = 0
for i,s in enumerate(S[::-1]):
  if s == '?':
    add_all_count[i%6] += 1
  else:
    constant_term += add_single[i%6][int(s)]

def convolve(x,y):
  z = np.zeros(25,dtype=np.int64)
  for i in range(13):
    z[i:i+13] += x[i] * y % MOD
  z[:12] += z[13:25]
  return z[:13] % MOD

def nth_convolve(arr,n):
  if n == 0:
    x = np.zeros(13, dtype=np.int64)
    x[0] = 1
    return x
  if n == 1:
    return arr
  x = nth_convolve(arr,n>>1)
  x = convolve(x,x)
  return convolve(arr,x) if n & 1 else x

dp = np.zeros(13, dtype=np.int64)
dp[constant_term % 13] = 1
for arr,n in zip(add_all, add_all_count):
  dp = convolve(dp, nth_convolve(arr,n))

print(dp[5])

Solution (Python):
s = input()
s = s[::-1]
n = len(s)
s = '
MOD = 10**9+7
dp = [[0]*13 for _ in range(n+5)]
"""
dp[i][j] は i 桁目まで見たとき 13 で割ったあまりが j　となるようなものの個数
"""
dp[0][0] = 1
r = 1 
for i in range(1,n+1):
    for j in range(13):
        if s[i] != '?':
            dp[i][j] = dp[i-1][(j-r*int(s[i]))%13] % MOD
        if s[i] == '?':
            for k in range(10):
                dp[i][j] += dp[i-1][(j-r*k)%13]
            dp[i][j] %= MOD
    r = (r*10) % 13
print(dp[n][5])

Solution (Python):
S = [int(x) if x != "?" else -1 for x in input()]
g = 10 ** 9 + 7
x = 1
DP = [[0] * 13 for _ in range(2)]
DP[0][0] = 1
for i in range(len(S)):
    DP[1], DP[0] = DP[0], DP[1]
    for j in range(13):
        DP[0][j] = 0
    for j in range(13):
        if S[i] == -1:
            s = (j*10)%13
            e = (s+10)%13
        else:
            s = (j*10+S[i])%13
            e = (s+1)%13
        DP[0][s] += DP[1][j]
        if s > e:
            DP[0][0] += DP[1][j]
        DP[0][e] -= DP[1][j]
    w = 0
    for j in range(13):
        w = (w + DP[0][j]) % g
        DP[0][j] = w

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

Solution (Python):
S = [int(x) if x != "?" else -1 for x in input()]
g = 10 ** 9 + 7
x = 1
DP = [[0] * 13 for _ in range(2)]
DP[0][0] = 1
for i in range(len(S)):
    for j in range(13):
        DP[1][j] = DP[0][j] % g
        DP[0][j] = 0
    for j in range(13):
        if S[i] == -1:
            s = (j*10)%13
            e = (s+10)%13
        else:
            s = (j*10+S[i])%13
            e = (s+1)%13
        DP[0][s] += DP[1][j]
        if s > e:
            DP[0][0] += DP[1][j]
        DP[0][e] -= DP[1][j]
    w = 0
    for j in range(13):
        w += DP[0][j]
        DP[0][j] = w

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

Solution (Python):

import sys
INF = float("inf")

MOD = 1000000007  


def solve(S: str):
    dp = [0]*13
    dp[0] = 1
    ep = [0]*13
    zero = [0]*13
    for c in S:
        ep[:] = zero
        for i in range(10):
            if c != "?" and int(c) != i:
                continue
            for j in range(13):
                ep[(10*j+i) % 13] += dp[j]
                ep[(10*j+i) % 13] %= MOD
        dp, ep = ep, dp

    print(dp[5])

    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):
def main():
    S = list(input())
    dp = [[0] * 13 for _ in range(10 ** 5 + 1)]
    dp[0][0] = 1
    n = len(S)
    for i in range(n):
        c = 0
        if S[i] == '?':
            c = -1
        else:
            c = int(S[i])
        for si in range(10):
            if c != -1 and c != si:
                continue
            for j in range(13):
                dp[i + 1][(j * 10 + si) % 13] += dp[i][j]
        for j in range(13):
            dp[i + 1][j] %= 10 ** 9 + 7
    print(dp[n][5])


main()

Solution (Python):
s = list(input().rstrip())
n = len(s)
m = 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 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] %= m
print(dp[n][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):
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():
    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])
main()

Solution (Python):
import sys
 
s= sys.stdin.readline().strip()

MOD=10**9+7
mmap= []
for i in range(6):
    b = 10**i % 13
    mmap.append( [ [ (b*i+j)%13 for i in range(1,10) ] for j in range(13) ] )

dp= [ 0 ] * 13
dp[0] = 1
j= 0
for c in reversed(s):
    tmp = dp.copy()
    
    if c=="0": pass
    elif c=="?":
        bset = mmap[j]
        for m,num in enumerate(tmp):
            if num==0: continue
            for idx in bset[m]: dp[idx]+=num
        
        for i in range(13): dp[i]%=MOD
    else:
        b= mmap[j][0][int(c)-1]
        for m in range(13):
            idx= (m+b)%13
            dp[idx]= tmp[m]
    
    if j==5: j=0
    else: j+=1

print(dp[5])

Solution (Python):
import numpy as np

s = input()
p = np.array([0]*13)
p[0] = 1

amari = [[0]*13 for _ in range(13)]
for j in range(10):
  for i in range(13):
    amari[i][(i*10+j)%13] += 1
M = np.array(amari)

for si in range(len(s)):
  a = np.array([0]*13)
  if s[si] == '?':
    a = np.dot(p,M)
  else:
    c = int(s[si])
    for i in range(13):
      a[(i*10+c)%13] += p[i]
  p = np.mod(a,1000000007)
print(p[5])

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

dp = np.zeros(13, dtype = np.int64)
dp[0] = 1

move = np.arange(0,52,4) % 13
ten = np.ones(10, dtype=np.int64)
for s in input():
  dp = dp[move]
  if s == '?':
    dp = np.convolve(dp, ten)
    dp[:9] += dp[13:22]
    dp %= MOD
  else:
    dp = np.roll(dp, int(s))
  
print(dp[5])

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

Solution (Python):



import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7

s = list(input())
s = s[::-1]
l = len(s)

dp = [[0]*13 for _ in range(l)]
remain = 1
if s[0] == '?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(s[0])] = 1

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

Solution (Python):
MOD = 10 ** 9 + 7
qTable = [[(j * i) % 13 for j in range(13)] for i in range(11)]

S = input()

C, tC, qi = [1] + [0] * 12, [0] * 13,  1

for i in range(len(S)):
    if S[-(i + 1)] == '?':
        tC = [0] * 13
        for j in range(10):
            q = qTable[j][qi]
            for c in range(13):
                tC[(c + q) % 13] += C[c]
    else:
        q = qTable[int(S[-(i + 1)])][qi]
        for c in range(13):
            tC[(c + q) % 13] = C[c]

    qi = qTable[10][qi]
    for c in range(13):
        C[c] = tC[c] % MOD

print(C[5] % MOD)