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



Sample input:
??2??5


Sample output:
768

Submission status: Accepted

Solution code:
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


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

Submission status: Accepted

Solution code:
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):
    #　i+1番目が？のときは０〜９の可能性
    if s[i]==-1:
      count+=1
      for k in range(10):
        dp[i+1][(j*10+k)%13]+=dp[i][j]
        

    #  i+1番目が?じゃないとき
    else:
      dp[i+1][(j*10+s[i])%13]+=dp[i][j]

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
M=10**9+7
#リストに入力（文字列）
text=input()
lst=list(text)
lst.reverse()
digit=len(lst)

######六桁ごとに区切って、?の数とその他の数字を数える
######たとえば文字列のリストが「9?????81????」だったら
######[[17,0],[8,1],[0,2],[0,2],[0,2],[0,2]]になる
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

    
######数字部分の余りから5を引く    
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

######漸化式を6個用意
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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)
print(dp[len(S)][5])

Submission status: Accepted

Solution code:
mod=10**9+7

S=input()

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

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)
print(dp[0][5]%mod)

Submission status: Accepted

Solution code:
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)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

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

# print(each_extras)

# print(extra)
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)
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)
print(dp[-1][5])
"""

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

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)
            # each_extras[cnt][x * 10 ** i % 13] = 1
        cnt += 1

# print(each_extras)

# print(extra)
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)
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)
print(dp[-1][5])

Submission status: Accepted

Solution code:
S = input()
N = len(S)
#dp[i][j] ... 先頭i文字として考えられるもののうち13で割った余りがjになる個数
dp = [[0] * 13 for _ in range(N+1)]
dp[0][0] = 1
mod = 10**9+7
#1?2?3   0 -> 3 -> ?3 -> 2?3 -> ...
mul = 1
for i in range(N): #全ての桁
    for k in range(13): #0~12
        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])
#print(dp)

Submission status: Accepted

Solution code:
S = str(input())

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

dp[0][0] = 1

for i in range(len(S)):  # Sへのアクセスは0-index
    for remain in range(13):
        if S[i] == '?':
            for j in range(10):
                next_remain = (remain*10 + j) % 13
                # dpの遷移
                dp[i+1][next_remain] += dp[i][remain]
                dp[i+1][next_remain] %= 1000000007
        else:
            next_remain = (remain*10 + int(S[i])) % 13
            # dpの遷移
            dp[i+1][next_remain] += dp[i][remain]
            dp[i+1][next_remain] %= 1000000007

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

Submission status: Accepted

Solution code:
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
#print(dp)
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])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#%%time
mod=10**9+7
s=input()


#p=[[i*j%13 for i in range(10)] for j in range(13)]
rev=reversed(s)
d=[0 for i in range(13)]
d[0]=1
keep=[0 for _ in range(13)]
mul=1
cal=0
for v in rev:
    #print(i+num+1)
    if v=="?":
        t_d=[0 for _ in range(13)]
        #print("i,tmp:",i+num+1,",",tmp)
        for k in range(0,13):
            for j in range(0,10):
                t_d[(mul*j+k)%13]+=d[k]
            t_d[k]%=mod
        d=t_d
    else:
        cal+=mul*int(v)%13
    mul*=10
    mul%=13
        #print(t_d)
cal%=13
if cal<=5:
    cal=5-cal
else:
    cal=18-cal
print(d[cal]%mod)
#print(d)
#h=d
#print([i%mod for i in h])

Submission status: Accepted

Solution code:
S = input()
dp = [[0]*13 for i in range(len(S))]
MOD = 10**9+7
 
if S[0]=='?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(S[0])] = 1
 
for i,c in enumerate(S[1:]):
    for j in range(13):
        if c=='?':
            for k in range(10):
                nj = (j*10 + k) % 13
                dp[i+1][nj] += dp[i][j]
                dp[i+1][nj] %= MOD
        else:
            nj = (j*10 + int(c)) % 13
            dp[i+1][nj] += dp[i][j]
            dp[i+1][nj] %= MOD
 
print(dp[-1][5])

Submission status: Accepted

Solution code:
import numpy as np
from numpy.fft import rfft, irfft
from itertools import cycle

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

mat = []
for i in range(6):
    w = np.zeros(13)
    for j in range(10):
        w[(10 ** i * j) % 13] += 1
    mat.append(rfft(w))

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


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

res = 5
for keta, s in zip(cycle(range(6)), S[::-1]):
    if s == "?":
        state = state * mat[keta]
        if state[0] >= 2 ** 50:
            state = np.round(irfft(state, 13))
            state = rfft(np.remainder(state, mod))
    else:
        res -= ress[keta][int(s)]


state = irfft(state, 13)
print(int(np.round(state[res % 13])) % mod)

Submission status: Accepted

Solution code:
import numpy as np
from numpy.fft import rfft, irfft
from itertools import cycle

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

mat = []
for i in range(6):
    w = np.zeros(13)
    for j in range(10):
        w[(10 ** i * j) % 13] += 1
    mat.append(rfft(w))

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


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

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

    if state[0] >= 2 ** 50:
        state = np.round(irfft(state, 13))
        state = rfft(np.remainder(state, mod))


state = irfft(state, 13)
print(int(np.round(state[res % 13])) % mod)

Submission status: Accepted

Solution code:
import numpy as np
from numpy.fft import rfft, irfft

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

mat = []
for i in range(6):
    w = np.zeros(13)
    for j in range(10):
        w[(10 ** i * j) % 13] += 1
    mat.append(rfft(w))

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


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

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

    if state[0] >= 2 ** 50:
        state = np.round(irfft(state, 13))
        state = rfft(np.remainder(state, mod))

    keta += 1

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

Submission status: Accepted

Solution code:
#N = "?"*(100000)
N = input()
digit = len(N)
mod = 1000000007

# dp[i番目まで][未満かどうか][mod13], 計算量O(10**5 * 2 * 13 * 10)
dp = [[[0]*13 for _ in range(2)] for _ in range(digit+1)]
dp[0][0][0] = 1

d = 1/10
for i in range(digit-1,-1,-1):
  ii = digit-i-1
  d = int((d*10)%13)
  for j in range(2):
    for k in range(13):
      if N[i] == "?":
        for n in range(9+1):
          dp[ii+1][j][(k + n*d) %13] += dp[ii][j][k] %mod
      else:
        n = int(N[i])
        dp[ii+1][j][(k + n*d) %13] += dp[ii][j][k] %mod

print((dp[digit][0][5] + dp[digit][1][5]) %mod)
#print(dp[-10:])