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: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
    
S = list(input())
length=len(S)
dp = [[0 for _ in range(13)] for _ in range(length)]
dp[0][0]=1
for i in range(length-1):
    if S[length-i-2] == "?":
        for k in range(10):
            for j in range(13):
                j_sub = j-k*10**i%13
                if j_sub < 0: j_sub+= 13
                dp[i+1][j]+=dp[i][j_sub]
    else:
        for j in range(13):
            j_sub = j-int(S[length-i-2])*10**i%13
            if j_sub < 0: j_sub+= 13
            dp[i+1][j]+=dp[i][j_sub]
print(dp[length-1][5]%1000000007)
for j in range(13):

Submission status: Runtime Error

Solution code:
S = input()

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

dp[0][0] = 1
for i, s in enumerate(S):
    if s != '?':
        for j in range(10):
            for k in range(13):
                dp[i+1][(k * 10 + j) % 13] += dp[i][k]
    else:
        s_int = int(s)
        for k in range(13):
            dp[i+1][(k * 10 + s_int) % 13] += dp[i][k]
        
    for j in range(13):
        dp[i+1][j] %= 10**9 + 7

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

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
S=list(input())
le=len(S)
dp=[[0 for i in range(13)] for j in range(le+1)]
dp[0][0] = 1

def xin(A,n):
    li=[0]*13
    for i in range(13):
        li[(i+n)%13] = A[i]%(10**9+7)
    return li


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

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


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

Submission status: Runtime Error

Solution code:
import numpy as np
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)

Submission status: Runtime Error

Solution code:
N=input()

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

dic={0:1}

for i in N:
    new_dic={}
    if i == "?":
        for amari,count in list(dic.items()):
            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:
        for amari,count in list(dic.items()):
            a = (amari*10 + num)%13
            if a in new_dic:
                new_dic[a]+=count
            else:
                new_dic[a]=count
    dic = new_dic

try:
    print(dic[5]%(10**9 + 7))
except:
    print(0)

Submission status: Runtime Error

Solution code:
import numpy as np
s=input()
M = 10**9+7
if s[0] == "?":
    pre = [1 if i<10 else 0 for i in range(13)]
else:
    pre=[0 for i in range(13)]
    pre[int(s[-1])] += 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
mask = np.array(amari)

for i in range(1, len(s)):
    if s[i] == "?":
        data = np.dot(pre, mask) % M
    else:
        c = int(s[i])
        data=np.array([0 for i in range(13)], dtype=np.int64)
        for k in range(13):
            data[(10*k+c)%13] += pre[k]
        data %= M
    pre = np.array(data.copy(), dtype=np.int64)
if len(s)==1:
    print(pre[5])
else:
    print(data[5])

Submission status: Runtime Error

Solution code:
s=input()
if s[-1] == "?":
    pre = [1 if i<10 else 0 for i in range(13)]
else:
    pre=[0 for i in range(13)]
    pre[int(s[-1])] += 1
for i in range(1, len(s)):
    data=[0 for i in range(13)]
    tmp = 10**i % 13
    if s[len(s)-1-i] == "?":
        for j in range(10):
            for k in range(13):
                data[(tmp*j+k)%13] += pre[k]
    else:
        tmp = tmp*int(s[len(s)-1-i]) % 13
        for k in range(13):
            data[(tmp+k)%13] += pre[k]
    pre = data.copy()
if len(s)==1:
    print(pre[5]%(10**9+7))
else:
    print(data[5]%(10**9+7))

Submission status: Runtime Error

Solution code:
s=input()
if s[-1] == "?":
    pre = [1 if i<10 else 0 for i in range(13)]
else:
    pre=[0 for i in range(13)]
    pre[int(s[-1])] += 1
for i in range(1, len(s)):
    data=[0 for i in range(13)]
    tmp = 10**i % 13
    if s[len(s)-1-i] == "?":
        for j in range(10):
            for k in range(13):
                data[(tmp*j+k)%13] += pre[k]
    else:
        tmp = tmp*int(s[len(s)-1-i]) % 13
        for k in range(13):
            data[(tmp+k)%13] += pre[k]
    pre = data.copy()
print(data[5]%(10**9+7))

Submission status: Runtime Error

Solution code:
from operator import itemgetter
import sys
input = sys.stdin.readline
 
S = input()
 
table = [[0] * 13 for i in range(len(S))]
 
if S[len(S)-1] == '?':
    for i in range(10):
        table[0][i] = 1
else:
    table[0][int(S[len(S)-1])] = 1
 
for i in range(len(S)-1):    
    if S[len(S)-i-2] =='?':
        for j in range(10):
            mod = (10**(i+1)) * j % 13
            for k in range(13):
                table[i+1][(k+mod) % 13] += table[i][k] #% (10**9 + 7)
    else:
        num = int(S[len(S)-i-2])
        mod = (10**(i+1)) * num % 13
        for k in range(13):
            table[i+1][(k+mod) % 13] += table[i][k] #% (10**9 + 7)
            
print(table[len(S)-1][5]%(10**9+7))

Submission status: Runtime Error

Solution code:
from operator import itemgetter
import sys
input = sys.stdin.readline

S = input()

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

if S[len(S)-1] == '?':
    for i in range(10):
        table[0][i] = 1
else:
    table[0][int(S[len(S)-1])] = 1

for i in range(len(S)-1):    
    if S[len(S)-i-2] =='?':
        for j in range(10):
            mod = (10**(i+1)) * j % 13
            for k in range(13):
                table[i+1][(k+mod) % 13] += table[i][k] #% (10**9 + 7)
    else:
        num = int(S[len(S)-i-2])
        mod = (10**(i+1)) * num % 13
        for k in range(13):
            table[i+1][(k+mod) % 13] += table[i][k] #% (10**9 + 7)
            
print(table[len(S)-1][5]%(10**9+7))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

S = input()
N = len(S)
mod_13 = [10 ** i % 13 for i in range(N)]
table = [[0] * 13 for _ in range(N + 1)]
table[0][0] = 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 + mod_13[i] * k)  % 13] += table[i][j]
            table[i+1][(j + mod_13[i] * k)  % 13] %= (10 ** 9 + 7)

print(table[N][5])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

S = input()
N = len(S)
mod_13 = [10 ** i % 13 for i in range(N)]

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

for i, char in enumerate(reversed(S)):
    next_dp = [0 for _ in range(13)]
    c = char != '?'
    for j in range(13):
        for k in range(10):
            if c and int(char) != k:
                continue
            next_dp[(j + mod_13[i] * k)  % 13] += dp[j]
    dp = list(map(lambda x: x % (10 ** 9 + 7), next_dp))

print(dp[5])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

S = input()
N = len(S)
mod_13 = [10 ** i % 13 for i in range(N)]

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

for i, char in enumerate(reversed(S)):
    next_dp = [0 for _ in range(13)]
    if char == '?':
        for j in range(13):
            for k in range(10):
                next_dp[(j + mod_13[i] * k)  % 13] += dp[j]
    else:
        offset = (int(char) * mod_13[i]) % 13
        for j in range(13):
            next_dp[(offset + j) % 13] = dp[j]
    dp = list(map(lambda x: x % (10 ** 9 + 7), next_dp))

print(dp[5])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

S = input()
N = len(S)
mod_13 = [10 ** i % 13 for i in range(N)]

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

for i, char in enumerate(reversed(S)):
    next_dp = [0 for _ in range(13)]
    if char == '?':
        for j in range(13):
            for k in range(10):
                next_dp[(j + mod_13[i] * k)  % 13] += dp[j]
    else:
        offset = (int(char) * mod_13[i]) % 13
        for j in range(13):
            next_dp[(offset + j) % 13] = dp[j]
    dp = next_dp[:]

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

Submission status: Runtime Error

Solution code:
inp = input()
arr = [[i for i in range(10)]]
for j in range(1,len(inp)):
    arr.append([])
    for i in range(10):
        arr[j].append((arr[j-1][i]*10)%13)
rem = 0
p = []
l = len(inp)
for i,c in enumerate(inp[::-1]):
    if c == '?':
        p.append(arr[i])
    else:
        rem += arr[i][int(c)]
rems = [0]*13
for i in p[0]:
    rems[i] += 1
if len(p)>1:
    for row in p[1:]:
        remsnew = [0]*13
        for i in row:
            for j,val in enumerate(rems):
                remsnew[(j+i)%13] += val
        rems = remsnew
print(rems[(5-rem)%13] % (10**9 + 7))

Submission status: Runtime Error

Solution code:
inp = input()
arr = []
for j in range(len(inp)):
    arr.append([])
    for i in range(10):
        arr[j].append(((10**j) * i)%13)
rem = 0
p = []
l = len(inp)
for i,c in enumerate(inp[::-1]):
    if c == '?':
        p.append(arr[i])
    else:
        rem += arr[i][int(c)]
rems = [0]*13
for i in p[0]:
    rems[i] += 1
if len(p)>1:
    for row in p[1:]:
        remsnew = [0]*13
        for i in row:
            for j,val in enumerate(rems):
                remsnew[(j+i)%13] += val
        rems = remsnew
print(rems[(5-rem)%13] % (10**9 + 7))

Submission status: Runtime Error

Solution code:
ip = list(str(input()))
a = [0]*len(ip)
for i in range(len(ip)):
    if ip[i] == "?":
        a[i] += 1
tmp = []
s = ""

def nums0(s):
    if len(s) < sum(a):
        s += "0"
        nums0(s)
        nums1(s)
        nums2(s)
        nums3(s)
        nums4(s)
        nums5(s)
        nums6(s)
        nums7(s)
        nums8(s)
        nums9(s)        
    else:
        tmp.append(s)
def nums1(s):
    if len(s) < sum(a):
        s += "1"
        nums0(s)
        nums1(s)
        nums2(s)
        nums3(s)
        nums4(s)
        nums5(s)
        nums6(s)
        nums7(s)
        nums8(s)
        nums9(s)        
    else:
        tmp.append(s)

def nums2(s):
    if len(s) < sum(a):
        s += "2"
        nums0(s)
        nums1(s)
        nums2(s)
        nums3(s)
        nums4(s)
        nums5(s)
        nums6(s)
        nums7(s)
        nums8(s)
        nums9(s)        
    else:
        tmp.append(s)

def nums3(s):
    if len(s) < sum(a):
        s += "3"
        nums0(s)
        nums1(s)
        nums2(s)
        nums3(s)
        nums4(s)
        nums5(s)
        nums6(s)
        nums7(s)
        nums8(s)
        nums9(s)        
    else:
        tmp.append(s)

def nums4(s):
    if len(s) < sum(a):
        s += "4"
        nums0(s)
        nums1(s)
        nums2(s)
        nums3(s)
        nums4(s)
        nums5(s)
        nums6(s)
        nums7(s)
        nums8(s)
        nums9(s)        
    else:
        tmp.append(s)

def nums5(s):
    if len(s) < sum(a):
        s += "5"
        nums0(s)
        nums1(s)
        nums2(s)
        nums3(s)
        nums4(s)
        nums5(s)
        nums6(s)
        nums7(s)
        nums8(s)
        nums9(s)        
    else:
        tmp.append(s)
    
def nums6(s):
    if len(s) < sum(a):
        s += "6"
        nums0(s)
        nums1(s)
        nums2(s)
        nums3(s)
        nums4(s)
        nums5(s)
        nums6(s)
        nums7(s)
        nums8(s)
        nums9(s)        
    else:
        tmp.append(s)
    
def nums7(s):
    if len(s) < sum(a):
        s += "7"
        nums0(s)
        nums1(s)
        nums2(s)
        nums3(s)
        nums4(s)
        nums5(s)
        nums6(s)
        nums7(s)
        nums8(s)
        nums9(s)        
    else:
        tmp.append(s)
    
    
def nums8(s):
    if len(s) < sum(a):
        s += "8"
        nums0(s)
        nums1(s)
        nums2(s)
        nums3(s)
        nums4(s)
        nums5(s)
        nums6(s)
        nums7(s)
        nums8(s)
        nums9(s)        
    else:
        tmp.append(s)
    
def nums9(s):
    if len(s) < sum(a):
        s += "9"
        nums0(s)
        nums1(s)
        nums2(s)
        nums3(s)
        nums4(s)
        nums5(s)
        nums6(s)
        nums7(s)
        nums8(s)
        nums9(s)        
    else:
        tmp.append(s)
if a[0] == 0:
    nums1(s)
    nums2(s)
    nums3(s)
    nums4(s)
    nums5(s)
    nums6(s)
    nums7(s)
    nums8(s)
    nums9(s)
else:
    nums0(s)
    nums1(s)
    nums2(s)
    nums3(s)
    nums4(s)
    nums5(s)
    nums6(s)
    nums7(s)
    nums8(s)
    nums9(s)
tmp = set(tmp)
ans = 0
#ip = [?,?,2,?,?,5]
#a  = [1,1,0,1,1,0]
for i in tmp:
    nums = list(i)
    tmpstr = ""
    jj = 0
    for j in range(len(ip)):
        if a[j] == 1:
            tmpstr += nums[jj]
            jj += 1
        else:
            tmpstr += ip[j]
    if int(tmpstr) % 13 == 5:
        ans += 1
ans = ans % (10**9 + 1)
print(ans)

Submission status: Runtime Error

Solution code:
s = input()
n = len(s)
mod = 10**9 + 7
dp = [[0 for i in range(n)] for j in range(13)]

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

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

for x in range(1,len(s)):
    for y in range(13):
        if s[x]=='?':
            for j in range(10):
                dp[(mod_change_table[y]+j)%13][x] += dp[y][x-1]
        else:
            dp[(mod_change_table[y]+int(s[x]))%13][x] += dp[y][x-1]
            

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

Submission status: Runtime Error

Solution code:
import numpy as np

P_MOD = 1000000007


def solve(S):
    # print(S)
    # 1, 10, 100, 1000, ... を 13 で割った値は 1, 10, 9, 12, 3, 4 で巡回する
    MODS = np.array([1, 10, 9, 12, 3, 4], dtype=np.int)

    # 現在の桁の余り N の状態を cur[N]
    # 直前の桁の余り N の状態を priv[N] とする
    priv = np.zeros(13, dtype=np.int)
    priv[0] = 1
    s = S[::-1]
    for i in range(0, len(s)):
        cur = np.zeros(13+13, dtype=np.int)
        d = s[i]
        if d == '?':
            for di in range(10):
                m = (di * MODS[i % 6]) % 13
                cur[m:m+13] = (cur[m:m+13] + priv[0:13]) % P_MOD
            cur[0:13] += cur[13:26]
        else:
            m = (int(d) * MODS[i % 6]) % 13
            cur[m:m+13] = priv[0:13]
            cur[0:13] += cur[13:26]
        priv = cur
    return cur[5]


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

    ans = solve(S)

    print(ans % P_MOD)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

P_MOD = 1000000007


def solve(S):
    # print(S)
    # 1, 10, 100, 1000, ... を 13 で割った値は 1, 10, 9, 12, 3, 4 で巡回する
    MODS = [1, 10, 9, 12, 3, 4]

    # 現在の桁の余り N の状態を cur[N]
    # 直前の桁の余り N の状態を priv[N] とする
    priv = [1] + [0] * 12
    # print(priv)
    s = S[::-1]
    for i in range(0, len(s)):
        cur = [0] * 13
        d = s[i]
        # print('i=', i, 'd=', d)
        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]
        # print(cur)
        for j in range(13):
            priv[i] = cur[i] % P_MOD
    return cur[5]


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

    ans = solve(S)

    print(ans % P_MOD)

Submission status: Runtime Error

Solution code:
#基本情報
S = input()
L = len(S)
c = int('9'*L)
d = int(c / 13)

dct = {6:76923,5:7692,4:769,3:76,2:7,1:1}

#候補リスト
lst = [str(i*13+5) for i in range(d)]
lst = list(map(lambda l:'0'*(L-len(l)) + l,lst))

#print(lst)

#照合プロセス
cnt = 0
for l in lst: #lはstr 候補を当たってく
	for s in range(L): #sはint Sを一文字ずつ当たる
		if S[s] == '?':
			pass
		else:
			#print('S[s]={},l[s]={}'.format(S[s],l[s]))
			if S[s] == l[s]:
				pass
			else:
				#print(l)
				cnt += 1
				break
		
print((len(lst)-cnt)%(10**9+7))

Submission status: Runtime Error

Solution code:
#基本情報
S = input()
L = len(S)
dct = {6:76923,5:7692,4:769,3:76,2:7,1:1}

#候補リスト
lst = [str(i*13+5) for i in range(dct[L])]
lst = list(map(lambda l:'0'*(L-len(l)) + l,lst))

#print(lst)

#照合プロセス
cnt = 0
for l in lst: #lはstr 候補を当たってく
	for s in range(L): #sはint Sを一文字ずつ当たる
		if S[s] == '?':
			pass
		else:
			#print('S[s]={},l[s]={}'.format(S[s],l[s]))
			if S[s] == l[s]:
				pass
			else:
				#print(l)
				cnt += 1
				break
		
print((len(lst)-cnt)%(10**9+7))

Submission status: Runtime Error

Solution code:
#基本情報
S = input()
L = len(S)
dct = {6:76923,5:7692,4:769,3:76,2:7,1:1}

#候補リスト
lst = [str(i*13+5) for i in range(dct[L])]
lst = list(map(lambda l:'0'*(L-len(l)) + l,lst))

#print(lst)

#照合プロセス
cnt = 0
for l in lst: #lはstr 候補を当たってく
	for s in range(L): #sはint Sを一文字ずつ当たる
		if S[s] == '?':
			pass
		else:
			#print('S[s]={},l[s]={}'.format(S[s],l[s]))
			if S[s] == l[s]:
				pass
			else:
				#print(l)
				cnt += 1
				break
		
print((len(lst)-cnt)%(10**9+7))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# from tqdm import tqdm

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

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

print(dp[5])

Submission status: Runtime Error

Solution code:
S=input()
length=len(s)
mod=[[0 for i in range(13)] for j in range(length)]
s=S[::-1]#一桁目が先頭に来た
if s[0]=="?":
    for i in range(10):
        mod[0][i]+=1
else:
    mod[0][int(s[0])]+=1
    #一桁目の設定をした

for n in range(length-1):#n桁目のことを考える nは0からlength-1まで
    p=(10**n)%13
    if s[n+1]=="?":
        list1=[0]*13
        for k in range(10):
            q=(k*p)%13
            list1[q]+=1#あまりがqの場合が何通りあるかを考えた
        for q in range(13):
            if list1[q]!=0:
                for k in range(13):
                    mod[n+1][k]+=(mod[n][(k-q+13)%13])*list1[q]
    else:
        q=(int(s[n+1])*p)%13
        for i in range(13):
            mod[n+1][i]+=mod[n][(i-q+13)%13]
    
    for i in range(13):
        mod[n+1][i]=(mod[n+1][i])%(10**9+7)
    
print(mod[length-1][6])

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import itertools

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

s = list(reversed(input()))
n = len(s)
mod = 10 ** 9 + 7
digits=[0]*n

for i in range(n):
    digits[i] = (10 ** i) % 13


cache = [[-1]*13 for _ in range(n+1)]

def solve(pos, now):
    if pos >= n:
        return 1 if now == 5 else 0
    res = cache[pos][now]
    if res >= 0:
        return res
    res = 0
    if s[pos] == '?':
        for i in range(10):
            m = (now + i * digits[pos]) % 13
            res += solve(pos + 1, m)
    else:
        d = ord(s[pos]) - ord('0')
        m = (now + d * digits[pos]) % 13
        res += solve(pos + 1, m)
    res %= mod
    cache[pos][now] = res

    return res

for i in range(n-1,0,-1):
    solve(0,0)

print(solve(0, 0))

Submission status: Runtime Error

Solution code:
s = input()
count = 0
for i in range(n - 1):
    if s[i:i+2] == "??":
        count += 1
ans = count * 7
print(ans)

Submission status: Runtime Error

Solution code:
P=[1,10,9,12,3,4]
def f(A,p,N):
    if p==0:return [1&(i in N) for i in range(13)]
    B=[0]*13
    for n in N:
        for i in range(13):
            c=(i+(n*P[p]))%13
            B[c]=(B[c]+A[i])%(10**9+7)
    return B
S=reversed(input())
A=[0]
p=0
for s in S
    if s=="?":A=f(A,p,range(10))
    else:A=f(A,p,[int(s)])
    p=(p+1)%6
print(A[5])

Submission status: Runtime Error

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

    amari_list = amari(n)
    l = len(amari_list)

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

    for i, s in enumerate(reversed(in_str)):
        if i == 0:
            continue
        if s == "?":
            shift_list = np.array([shift(j * amari_list[i % l] % n, ans_list)
                                   for j in range(10)], dtype='int64')

            ans_list = np.mod(np.sum(shift_list, axis=0), mod)

        else:
            t = int(s) * amari_list[i % l] % n
            ans_list = shift(t, ans_list)

    print(ans_list[r] % mod)


def shift(r, num_list):
    l = len(num_list)
    return np.array([num_list[(i + l - r) % l] for i in range(l)], dtype='int64')


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 amari(n):
    ret = []
    for i in range(n+1):
        r = (10**i) % n
        if r in ret:
            return ret
        else:
            ret.append(r)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

    amari_list = amari(n)
    l = len(amari_list)

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

    for i, s in enumerate(reversed(in_str)):
        if i == 0:
            continue
        if s == "?":
            shift_list = [shift(j * amari_list[i % l] % n, ans_list)
                          for j in range(10)]

            ans_list = add(shift_list, mod)

        else:
            t = int(s) * amari_list[i % l] % n
            ans_list = shift(t, ans_list)

    print(ans_list[r] % mod)


def shift(r, num_list):
    l = len(num_list)
    return np.array([num_list[(i + l - r) % l] for i in range(l)], dtype='int64')


def add(num_list, mod):
    return np.sum(num_list, axis=0) % mod


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


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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
S = input()[::-1]

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

for i in range(1,len(S)+1):
  s = S[i-1]
  dp += [[0]*13]
  if s=='?':
    for j in range(13):
      for h in range(10):
        x = h*(10**(i-1))%13
        dp[i][(j+x)%13] += dp[i-1][j]
    for j in range(13):
      dp[i][j] = dp[i][j]%MOD
  else:
    c = int(s)
    x = c*(10**(i-1))%13
    for j in range(13):
      dp[i][(j+x)%13] = dp[i-1][j]
    for j in range(13):
      dp[i][j] = dp[i][j]%13
print(dp[-1][5])

Submission status: Runtime Error

Solution code:
s=input()
l=len(s);mod=10**9+7
dp=[[0]*13 for i in range(n)]
rem=[1,10,9,12,3,4]
for i in range(n)[::-1]:
  dig=i%6
  if s[i]=="?":
    if i==n-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
print(dp[0][5])

Submission status: Runtime Error

Solution code:
s=input()
mod = 1000000007

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

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

Submission status: Runtime Error

Solution code:
import numpy as np
s=list(input())

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

if s[-1] == '?':
    mod_list = [1,1,1,1,1,1,1,1,1,1,0,0,0]
else:
    mod_list = [0 for _ in range(13)]
    mod_list[int(s[-1])] = 1
for i in range(1,len(s)):
    old_mod_list = mod_list
    mod_list = [0 for _ in range(13)]
    if s[-(1+i)] != '?':
        a = s[-(1+i)]
        new = (ten_list[int(i%6)] * int(a)) % 13
        for j in range(13):
            new1 = (j + new) % 13
            mod_list[new1] += old_mod_list[j]
    else:
        for k in range(10):
            new = (ten_list[int(i%6)] * k) % 13
            for j in range(13):
                new1 = (j + new) % 13
                mod_list[new1] += old_mod_list[j]            
print(int(mod_list[5]%(1e9+7)))

Submission status: Runtime Error

Solution code:
#goalまでNます
S = list(input())

cnt = S.count("?")
list = []

for i in range(len(S)):

    if S[i]=="?":
        list.append(i)
    else:
       S[i] = int(S[i])
count = []



def search(n, k, S):

    #最後まできた時
    if n==cnt:
        S[list[n-1]] = k

        test = 0
        for i in range(len(S)):
            test = test + S[i]*10**(len(S)-i-1)
        if (int(test) % 13) == 5:
            count.append(1)
        return

    S[list[n-1]] = k

    for i in range(0, 10, 1):
        search(n+1, i, S)

for i in range(0, 10, 1):
    search(1, i, S)

print(len(count)%(7+10**9))

Submission status: Runtime Error

Solution code:
#goalまでNます
S = list(input())

cnt = S.count("?")
list = []

for i in range(len(S)):

    if S[i]=="?":
        list.append(i)
    else:
       S[i] = int(S[i])
count = []



def search(n, k, S):

    #最後まできた時
    if n==cnt:
        S[list[n-1]] = k

        test = 0
        for i in range(len(S)):
            test = test + S[i]*10**(len(S)-i-1)
        if (int(test) % 13) == 5:
            count.append(1)
        return

    S[list[n-1]] = k

    for i in range(0, 10, 1):
        search(n+1, i, S)

for i in range(0, 10, 1):
    search(1, i, S)

print(len(count))

Submission status: Runtime Error

Solution code:
#goalまでNます
S = list(input())

cnt = S.count("?")
list = []

for i in range(len(S)):

    if S[i]=="?":
        list.append(i)
    else:
       S[i] = int(S[i])
count = []

print(list)


def search(n, k, S):

    #最後まできた時
    if n==cnt:
        S[list[n-1]] = k
        print(S)
        test = 0
        for i in range(len(S)):
            test = test + S[i]*10**(len(S)-i-1)
        if (int(test) % 13) == 5:
            count.append(1)
        return

    S[list[n-1]] = k

    for i in range(0, 10, 1):
        search(n+1, i, S)

for i in range(0, 10, 1):
    search(1, i, S)

print(len(count))

Submission status: Runtime Error

Solution code:
N = int(input())
H = list(map(int, input().split()))

flag = "Yes"
for i in range(N-1,0,-1):
  if H[i-1] - H[i] > 1:
    flag = "No"
    break;
  elif H[i-1] - H[i] == 1:
    H[i-1] -= 1
for i in range(N-1):
  if H[i] - H[i+1] > 0:
    flag = "No"
    break;    
  
print (flag)

Submission status: Runtime Error

Solution code:
import numpy as np
M = 10**9+7
s = input()
n = len(s)
k = [0,0,0,0,0,0,0,0,0,0,0,0,0]
if s[0] == "?":
  k = [1,1,1,1,1,1,1,1,1,1,0,0,0]
else:
  k[int(s[0])] = 1
dp = np.array(k)

#行列生成
arr = []
for i in range(13):
  k = [1,1,1,1,1,1,1,1,1,1,1,1,1]
  y = 3*(12-i)
  l = [y%13,(y+1)%13,(y+2)%13]
  for j in l:
    k[j] = 0
  arr.append(k)
arr = np.array(arr)

for i in range(1,n):
  st = (i-1)*13
  if s[i] == "?":
    dp = np.append(dp,np.dot(dp[st:st+13],arr))
  else:
    l = np.array([0,0,0,0,0,0,0,0,0,0,0,0,0])
    for j in range(13):
      k = (j*10 + int(s[i]))%13
      l[k] += dp[st+j]
    dp = np.append(dp,l)
print(dp[st+18]%M)

Submission status: Runtime Error

Solution code:
S = input()

origin = S
dp = [1,0,0,0,0,0,0,0,0,0,0,0,0]

dig = 1
from operator import add
for s in reversed(origin):
    if s == '?':
        nums = list(range(10))
    else:
        nums = [int(s)]
        
    tmp = [0,0,0,0,0,0,0,0,0,0,0,0,0]
    #for i in range(13):
    #    for n in nums:
    #        tmp[(n*dig+i)%13] += dp[i]
    for n in nums:
        m = (n*dig+i)%13
        tmp = list(map(add, tmp, dp[m:]+dp[:m]))
    dp = tmp
    dig = dig * 10
ans = dp[5] % (10**9+7)
print(ans)