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:
def main():
  import numpy as np
  s = input()
  n = len(s)
  ans = [0 for i in range(13)]
  ans[0] = 1
  
  for i in range(n):
    tmp = [0 for i in range(13)]
    if s[i] == "?":
      for i in range(10):
        num = i*(10**(n-i-1)%13)
        tmp = np.add(tmp,np.roll(ans,num))
    else:
      num = int(s[i])*(10**(n-i-1)%13)
      #print("A",np.roll(ans,num))
      tmp = np.roll(ans,num)
      #print("tmp",tmp)
    ans = [tmp[i] for i in range(len(tmp))]
      
      
  #print(ans)
  print(ans[5])
 

if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

S = str(input())
'''
maxs = int(S.replace('?','9'))
div = maxs//13
counter = 0
'''
a = []
now = 0
for i in range(len(S)):
  if S[i]=='?':
    b = []
    for j in range(10):
      b.append((j*10**(len(S)-i-1) %13))
    a.append(b)
  else:
    now = (now+10**(len(S)-i-1)*int(S[i])) %13

counter = 0

dp=[[0 for j in range(13)] for i in range(len(a))]
for i in range(len(a)):
    if i==0:
      ## i==0のときの処理###
      for k in range(10):
        dp[i][(now+a[i][k])%13] = 1
      #####################
    else:
      for k in range(10):
        temp = a[i][k]
        for l in range(13):
          dp[i][(l+temp)%13] += dp[i-1][l]
          dp[i][(l+temp)%13] = dp[i][(l+temp)%13]%mod
print(dp[len(a)-1][5])


'''
from itertools import product
c=list(product([i for i in range(10)],repeat=len(a)))
#print(c)

for c1 in c:
  now2 = now
  for i in range(len(a)):
    now2 = (now2+a[i][c1[i]])%13
  if i==len(a)-1 and now2==5:
    counter = (counter+1)%mod

print(counter)
'''

Submission status: Runtime Error

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

mod = 10 ** 9 + 7

keta = 0
res = 5
state = [1] + [0] * 12
for s in reversed(input()):
    if s == "?":
        new_state = [0] * 13
        for i in range(13):
            for r in ress[keta]:
                new_state[i] += state[(i - r) % 13]

        state = new_state
    else:
        res -= ress[keta][int(s)]

    if keta == 5:
        keta = 0
        for i in range(13):
            new_state[i] %= mod
    else:
        keta += 1


print(state[res % 13] % mod)

Submission status: Runtime Error

Solution code:
N=input()
a=1000000000+7
b=[]
for i in N:
    if i=='?':b.append("9")
    else:b.append(i)
b=int(b)
print((b-5)/13%a)

Submission status: Runtime Error

Solution code:
s = input()
count = 0
k = 0
for i in s:
    if i == "?":
        k += 1
    else:
        break
for i in range(10**(len(s)-k-1), 10**(len(s))):
    if i % 13 == 5:
        flag = True
        i_str = str(i)
        if len(i_str) < len(s):
            i_str = "0" * (len(s) - len(i_str)) + i_str
        for j in range(len(s)):
            if s[j] == "?" or i_str[j] == s[j]:
                continue
            else:
                flag = False
                break
        if flag == True:
            count += 1
print(count % (10**9 + 7))

Submission status: Runtime Error

Solution code:
import itertools
s = input()
one = [0]
two = [0]
frag = 0
cnt = 0
if(len(s) % 3 == 0):
    for i in range(len(s) // 3):
        tmp = s[3*i:(3*i)+3]
        kuwaeru = []
        if(tmp[0] == '?'):
            if(tmp[1] == '?'):
                if(tmp[2] == '?'):
                    kuwaeru = [i for i in range(1, 1000)] #111
                else:
                    nani = int(tmp[2])
                    for i in range(10):
                        for j in range(10):
                            kuwaeru.append(i*100 + j * 10 + nani) #110
            elif(tmp[2] == '?'):
                mo = int(tmp[1]) * 10
                for i in range(10):
                    for j in range(10):
                        kuwaeru.append(i*100 + mo + j) #101
            else:
                kusa = int(tmp[1]) * 10 + int(tmp[2])
                for i in range(10):
                    kuwaeru.append(i*100 + kusa) #100
        elif(tmp[1] == '?'):
            if(tmp[2] == '?'):
                peya = int(tmp[0]) * 100
                for i in range(10):
                    for j in range(10):
                        kuwaeru.append(mo + i*10 + j) #011
            else:
                moyo = int(tmp[0]) * 100 + int(tmp[2])
                for i in range(10):
                    kuwaeru.append(moyo + i*10) #010
        elif(tmp[2] == '?'):
            aaa = int(tmp[0]) * 100 + int(tmp[1]) * 10
            for i in range(10):
                kuwaeru.append(aaa + i) #001
        else:
            aaaa = int(tmp)
            kuwaeru.append(aaaa) #000
        if(frag == 0):
            tmp = one
            one = []
            for i in range(len(tmp)):
                for j in range(len(kuwaeru)):
                    one.append(tmp[i]+kuwaeru[j])
            one = list(set(one))
            frag = 1
        else:
            tmp = two
            two = []
            for i in range(len(tmp)):
                for j in range(len(kuwaeru)):
                    two.append(tmp[i]+kuwaeru[j])
            two = list(set(two))
            frag = 0
        cnt += 1
elif(len(s) % 3 == 1):
    tmp = s[0]
    if(tmp == '?'):
        one = [i for i in range(9)]
    else:
        one = [int(tmp)]
    for i in range(1, (len(s) // 3)+1):
        tmp = s[3*i+1:(3*i)+4]
        kuwaeru = []
        if(tmp[0] == '?'):
            if(tmp[1] == '?'):
                if(tmp[2] == '?'):
                    kuwaeru = [i for i in range(1, 1000)] #111
                else:
                    nani = int(tmp[2])
                    for i in range(10):
                        for j in range(10):
                            kuwaeru.append(i*100 + j * 10 + nani) #110
            elif(tmp[2] == '?'):
                mo = int(tmp[1]) * 10
                for i in range(10):
                    for j in range(10):
                        kuwaeru.append(i*100 + mo + j) #101
            else:
                kusa = int(tmp[1]) * 10 + int(tmp[0])
                for i in range(10):
                    kuwaeru.append(i*100 + kusa) #100
        elif(tmp[1] == '?'):
            if(tmp[2] == '?'):
                peya = int(tmp[0]) * 100
                for i in range(10):
                    for j in range(10):
                        kuwaeru.append(mo + i*10 + j) #011
            else:
                moyo = int(tmp[0]) * 100 + int(tmp[2]) * 1
                for i in range(10):
                    kuwaeru.append(moyo + i*10) #010
        elif(tmp[2] == '?'):
            aaa = int(tmp[0]) * 100 + int(tmp[1]) * 10
            for i in range(10):
                kuwaeru.append(aaa + i) #001
        else:
            aaaa = int(tmp)
            kuwaeru.append(aaaa) #000
        if(frag == 0):
            tmp = two
            two = []
            for i in range(len(tmp)):
                for j in range(len(kuwaeru)):
                    two.append(tmp[i]+kuwaeru[j])
            two = list(set(two))
            frag = 1
        else:
            tmp = one
            one = []
            for i in range(len(tmp)):
                for j in range(len(kuwaeru)):
                    one.append(tmp[i]+kuwaeru[j])
            one = list(set(one))
            frag = 0
        cnt += 1
else:
    tmp = s[:2]
    if(tmp[0] == '?'):
        if(tmp[1] == '?'):
            one = [i for i in range(100)]
        else:
            aa = int(tmp[1])
            for i in range(10):
                one.append(i*10 + aa)
    elif(tmp[1] == '?'):
        aaa = int(tmp[0]) * 10
        for i in range(10):
            one.append(aaa + i)
    else:
        one = [int(tmp)]
    for i in range(len(s) // 3):
        tmp = s[3*i:(3*i)+3]
        kuwaeru = []
        if(tmp[0] == '?'):
            if(tmp[1] == '?'):
                if(tmp[2] == '?'):
                    kuwaeru = [i for i in range(1, 1000)] #111
                else:
                    nani = int(tmp[2])
                    for i in range(10):
                        for j in range(10):
                            kuwaeru.append(i*100 + j * 10 + nani) #110
            elif(tmp[2] == '?'):
                mo = int(tmp[1]) * 10
                for i in range(10):
                    for j in range(10):
                        kuwaeru.append(i*100 + mo + j) #101
            else:
                kusa = int(tmp[1]) * 10 + int(tmp[0])
                for i in range(10):
                    kuwaeru.append(i*100 + kusa) #100
        elif(tmp[1] == '?'):
            if(tmp[2] == '?'):
                peya = int(tmp[0]) * 100
                for i in range(10):
                    for j in range(10):
                        kuwaeru.append(mo + i*10 + j) #011
            else:
                moyo = int(tmp[0]) * 100 + int(tmp[2]) * 1
                for i in range(10):
                    kuwaeru.append(moyo + i*10) #010
        elif(tmp[2] == '?'):
            aaa = int(tmp[0]) * 100 + int(tmp[1]) * 10
            for i in range(10):
                kuwaeru.append(aaa + i) #001
        else:
            aaaa = int(tmp)
            kuwaeru.append(aaaa) #000
        if(frag == 0):
            tmp = two
            two = []
            for i in range(len(tmp)):
                for j in range(len(kuwaeru)):
                    two.append(tmp[i]+kuwaeru[j])
            two = list(set(two))
            frag = 1
        else:
            tmp = one
            one = []
            for i in range(len(tmp)):
                for j in range(len(kuwaeru)):
                    one.append(tmp[i]+kuwaeru[j])
            one = list(set(one))
            frag = 0
        cnt += 1
numa = [0 for i in range(13)]
numb = [0 for i in range(13)]

for i in range(len(one)):
    numa[one[i] % 13] += 1
for i in range(len(two)):
    numb[two[i] % 13] += 1

ans = 0
for i in range(13):
    ans += numa[(i+5)%13] * numb[i]
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

ls = [0,4,8,12,3,7,11,2,6,10,1,5,9]
S = input()
dp = [[None]*13 for _ in range(len(S))]
mod = 10**9+7
def f(i, r):
    if dp[i][r] != None:
        return dp[i][r]
    if i == 0:
        if S[0] == "?":
            dp[i][r] = 1 if r <= 9 else 0
            return dp[i][r]
        else:
            dp[i][r] = 1 if int(S[0]) == r else 0
            return dp[i][r]
    if S[i] != "?":
        c = int(S[i])
        tmp = (r-c) % 13
        dp[i][r] = f(i-1, ls[tmp]) % mod 
        return dp[i][r]
    else:
        ans = 0
        for j in range(10):
            tmp = (r-j) % 13
            ans = (ans +f(i-1, ls[tmp])) % mod
        dp[i][r] = ans % mod
        return dp[i][r]

print(f(len(S)-1, 5))

Submission status: Runtime Error

Solution code:
N=input()
a=1000000000+7
b=[]
for i in N:
    if i=='?':b.append("9")
    else:b.append(i)
b=int(b)
print((b-5)/13)

Submission status: Runtime Error

Solution code:
S = input()
list_s = list(reversed(list(S)))
small_s = int(S.replace('?', '0'))
L = 0
t = []
for i, s in enumerate(list_s):
    if s == '?':
        L += 1
        t.append(i)

count = 0
d = small_s % 13
for l in range(10**L):
    list_l = list(reversed(list(str(l))))
    temp = d
    for i, a in enumerate(list_l):
        temp += int(a)*(10**t[i])
    if temp % 13 == 5:
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
N=input()
a=1000000000+7
b=[]
for i in N:
    if i=='?':b.append(9)
    else:b.append(i)
b=int(b)
print((b-5)/13)

Submission status: Runtime Error

Solution code:
def main():
    mod=1000000007
    S=input()
    l=len(s)
    DP=[[0]*13 for _ in range(l+1)]
    DP[0][0]=1
    for i in range(1,l+1):
        d=s[-i]
        tmp=pow(10,i-1,13)
        if d=='?':
            for j in range(10):
                for k in range(13):
                    m=(k+tmp*j)%13
                    DP[i][m]+=DP[i-1][k]
                    if DP[i][m]>=mod:
                        DP[i][m]-=mod
        else:
            d=int(d)
            for k in range(13):
                m=(k+tmp*d)%13
                DP[i][m]+=DP[i-1][k]
                if DP[i][m]>=mod:
                    DP[i][m]-=mod
    print(DP[-1][5])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
s=input()
s=list(s)
l=len(s)
g=int(((10**(l)-1)-5)/13)+1
t=[]
tn=[]
ct=0
ans=0
for i in range(l):
    if s[i]!='?':
        t.append(int(s[i]))
        tn.append(l-i)
for i in range(l):
    if s[i]!='?':
        f=int((10**(l-i-1)-5)*int(s[i])/13)+1
        break
for i in range(f,g):
    num=13*i+5
    num=str(num)
    ct=0
    for j in range(len(tn)):
        if num[len(num)-tn[j]]==s[l-tn[j]]:
            ct+=1
    if ct==len(tn):
        ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
s=input()
s=list(s)
l=len(s)
g=int(((10**(l)-1)-5)/13)+1
t=[]
tn=[]
ct=0
ans=0
for i in range(l):
    if s[i]!='?':
        t.append(int(s[i]))
        tn.append(l-i)
for i in range(l):
    if s[i]!='?':
        f=int((10**(l-i-1)-5)/13)+1
        break
for i in range(f,g):
    num=13*i+5
    num=str(num)
    ct=0
    for j in range(len(tn)):
        if num[len(num)-tn[j]]==s[l-tn[j]]:
            ct+=1
    if ct==len(tn):
        ans+=1
print(ans)

Submission status: Runtime Error

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

MOD = 1000000007  # type: int

def compWithQues(S, number):
    N = len(number)
    for i in range(N):
        if S[i] == '?':
            continue
        if S[i] != number[i]:
            return False
    return True

def solve(S: str):
    largest = int(S.replace('?', '9')) - 5
    smallest = int(S.replace('?', '0')) - 5
    hi = largest // 13
    lo = smallest // 13
    S = S[::-1]
    count = 0
    for multi in range(lo, hi + 1):
        myint = str(13 * multi + 5)[::-1]
        if compWithQues(S, myint):
            count += 1
    print(count % MOD)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math

S = input()
l = len(S)

N = math.ceil((10**(l) - 5)/13)

for i,s in enumerate(list(S)):
     if s != "?" and s!=0:
        break
        
start = math.ceil((10**(l-i-1) - 5)/13)

tmp = "{:0=" + str(l) + "}"
can = [tmp.format(13*i + 5) for i in range(start,N+1)]
cnt = 0
for c in can:
    for i, (a,b) in enumerate(zip(list(c), list(S))):
        if b == "?":
            pass
        elif a == b:
            pass
        else:
            cnt -= 1
            break
    cnt += 1 

print(cnt%(10**9+7))

Submission status: Runtime Error

Solution code:

S=input()
l=len(S)
nhatena=0
for s in S:
    if s != '?':
        break
    nhatena += 1

min = 10**(l-1-nhatena)
max = 10**(l)-1

# print(min)
# print(max)

mink = int((min - 5) /13) + 1 if not ((min - 5) /13.0).is_integer() else int((min - 5) /13)
maxk = int((max - 5) / 13) + 1 if not ((max - 5) /13.0).is_integer() else int((max - 5) /13)

# print(mink)
# print(maxk)

cnt=0
for k in range(mink, maxk):
    v = 13 * k + 5
    val = ("%0" + str(l) + "d") % (v)
    #Sとの一致判定
    for i,s in enumerate(S):
        if s != '?':
            if s != val[i]:
                break
    else:
        cnt += 1

    if cnt == 1000000007:
        cnt = 0

print(cnt)

Submission status: Runtime Error

Solution code:
s = input()
n = len(s)

cnt = 0 
qnum = 0
ls = [0 for i in range(n)]
for i,v in enumerate(s):
  if v=="?":
    ls += [i]
    qnum +=1

num = int(s.replace("?","0"))
for i in range(10**qnum):
  for j,v in enumerate(ls):
    new_num = num + (i//10**(qnum-j-1))*10**(n-v-1)
    i = i%(10**qnum-j-1)

  if (int(new_num)%13==5):
    cnt+=1
    
print(cnt%(10**9+7))

Submission status: Runtime Error

Solution code:
import copy
S = list(input())

nums = [S]
def rec(i):
    global nums
    if i == len(S):
        return 0
    if S[i] == "?":
        tmpnums = copy.deepcopy(nums)
        nums = []
        for n in tmpnums:
            for j in range(10):
                if len(n[i+1:]) > 0:
                    k = n[:i]
                    k.append(str(j))
                    k.extend(n[i+1:])
                else:
                    k = n[:i]
                    k.append(str(j))
                nums.append(k)
        rec(i+1)
    else:
        rec(i+1)
rec(0)
c = 0
for n in nums:
    if int(''.join(n)) % 13 == 5:
        c += 1
print (c % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:

S=input()
l=len(S)
nhatena=0
for s in S:
    if s != '?':
        break
    nhatena += 1

min = 10**(l-1-nhatena)
max = 10**(l)-1

# print(min)
# print(max)

mink = int((min - 5) /13) + 1 if not ((min - 5) /13.0).is_integer() else int((min - 5) /13)
maxk = int((max - 5) / 13) + 1 if not ((max - 5) /13.0).is_integer() else int((max - 5) /13)

# print(mink)
# print(maxk)

cnt=0
for k in range(mink, maxk):
    v = 13 * k + 5
    val = ("%0" + str(l) + "d") % (v)
    print(val)
    #Sとの一致判定
    for i,s in enumerate(S):
        if s != '?':
            if s != val[i]:
                break
    else:
        cnt += 1

    if cnt == 1000000007:
        cnt = 0

print(cnt)

Submission status: Runtime Error

Solution code:
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

unsigned long M = 1000000007;

int main(void){
	unsigned char* buffer = malloc(100010);
	fgets(buffer, 100010, stdin);
	
	unsigned int* q_list = malloc(sizeof(int) * 100000);
	unsigned int q_count = 0;
	unsigned int num = 0;
	unsigned int d = 1;
	
	unsigned int len = strlen(buffer);
	while(1){
		unsigned char c = buffer[len - 1];
		if((c >= '0' && c <= '9') || c == '?'){
			break;
		}
		len --;
	}
	for(int i = len - 1; i >= 0; i --){
		unsigned char c = buffer[i];
		if(c == '?'){
			q_list[q_count ++] = d;
		}else{
			num = (num + (c - '0') * d) % 13;
		}
		d = (d * 10) % 13;
	}
	free(buffer);
	
	unsigned long counts_buffer[2][13];
	unsigned int b = 0;
	unsigned long *counts = counts_buffer[b];
	for(int i = 0; i < 13; i ++){
		counts[i] = 0;
	}
	counts[0] = 1;
	
	for(int j = 0; j < q_count; j ++){
		unsigned int d = q_list[j];
		unsigned long *new_counts = counts_buffer[1 - b];
		for(int i = 0; i < 13; i ++){
			new_counts[i] = 0;
		}
		for(int n = 0; n < 10; n ++){
			unsigned int r = (d * n) % 13;
			for(int m = 0; m < 13; m ++){
				unsigned int k = (r + m) % 13;
				new_counts[k] = (new_counts[k] + counts[m]) % M;
			}
		}
		b = 1 - b;
		counts = counts_buffer[b];
	}
	printf("%ld\n", counts[(13 + 5 - num) % 13]);
	return 0;
}
/*

M = 10 ** 9 + 7
s = input().strip()

num = 0
q_list = []
d = 1
l = len(s)
for i in range(l - 1, -1, -1):
	c = s[i]
	if c != "?":
		num = (num + int(c) * d) % 13
	else:
		q_list.append(d)
	d = (d * 10) % 13

counts = [0] * 13
counts[0] = 1
for d in q_list:
	new_counts = [0] * 13
	for n in range(10):
		r = (d * n) % 13
		for m in range(13):
			k = (r + m) % 13
			new_counts[k] = (new_counts[k] + counts[m]) % M
	counts = new_counts
print(counts[(13 + 5 - num) % 13])
*/

Submission status: Runtime Error

Solution code:
sys.setrecursionlimit(1000000)
S = input()
Ls = [1, 10, 9, 12, 3, 4]  # 10^n % 13, n % 6でループ

L = len(S) - 1
mem = [[-1 for _ in range(13)] for _ in range(len(S))]


def calc(i, m):  # i桁目以下で余りがmとなるようにする
    if mem[i][m] >= 0:
        return mem[i][m]
    t = S[L - i]
    if t == '?':
        if i == 0:
            if m < 10:
                mem[i][m] = 1
                return 1
            else:
                mem[i][m] = 0
                return 0
        else:
            s = 0
            for j in range(10):
                tm = m - ((Ls[i % 6] * j) % 13)
                if tm < 0:
                    tm += 13
                s += calc(i - 1, tm)
            mem[i][m] = s
            return s
    else:
        tn = int(t)
        if i == 0:
            if m == tn:
                mem[i][m] = 1
                return 1
            else:
                mem[i][m] = 0
                return 0
        else:
            tm = m - ((Ls[i % 6] * tn) % 13)
            if tm < 0:
                tm += 13
            k = calc(i - 1, tm)
            mem[i][m] = k
            return k


print(calc(len(S) - 1, 5) % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
S = input()
N = len(S)
DP =[0]*13
DP[0] = 1
A = 0
MOD = 10**9+7

B = [[0]*13 for i in range(13)]
for i in range(13):
    for j in range(13):
        B[i][j] = (i*j)%13
T = [1,10,9,12,3,4]
A = 0
for i in range(N):
    A*=10
    if S[i] == "?":
        hoge = [0]*13
        for j in range(13):
            for k in range(10):
                hoge[(j+k*T[(N-i-1)%6])%13] = (hoge[(j+k*T[(N-i-1)%6])%13] + DP[j])%MOD
        DP = hoge.copy()
    else:
        A = (A+int(S[i]))%13
print(DP[(A+5)%13])

Submission status: Runtime Error

Solution code:
S = input()
Ls = [1, 10, 9, 12, 3, 4]  # 10^n % 13, n % 6でループ

L = len(S) - 1
mem = [[-1 for _ in range(13)] for _ in range(len(S))]


def calc(i, m):  # i桁目以下で余りがmとなるようにする
    if mem[i][m] >= 0:
        return mem[i][m]
    t = S[L - i]
    if t == '?':
        if i == 0:
            if m < 10:
                mem[i][m] = 1
                return 1
            else:
                mem[i][m] = 0
                return 0
        else:
            s = 0
            for j in range(10):
                tm = m - ((Ls[i % 6] * j) % 13)
                if tm < 0:
                    tm += 13
                s += calc(i - 1, tm)
            mem[i][m] = s
            return s
    else:
        tn = int(t)
        if i == 0:
            if m == tn:
                mem[i][m] = 1
                return 1
            else:
                mem[i][m] = 0
                return 0
        else:
            tm = m - ((Ls[i % 6] * tn) % 13)
            if tm < 0:
                tm += 13
            k = calc(i - 1, tm)
            mem[i][m] = k
            return k


print(calc(len(S) - 1, 5) % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
def mod_check(i):
    if(i%13==5):
        flag=1
    else:
        flag=0
    return flag

def same(i,S):
    flag=1
    str_i=str(i)
    for j in range(len(S)-len(str_i)):
        str_i="0"+str_i

    for k in range(len(S)):
        if(str_i[k]==S[k] or S[k]=="?"):
            continue
        else:
            flag=0
            break
    return flag


S=input()
count=0
max_num=[]
for i in S:
    if(i=="?"):
        max_num.append(9)
    else:
        max_num.append(int(i))


max_number=0
digit=10**(len(max_num)-1)
for j in max_num:
    max_number+=j*digit
    digit/=10
max_number=int(max_number)

for i in range(max_number):
    mod_check_flag=mod_check(i)
    same_flag=same(i,S)
    check=mod_check_flag*same_flag
    if(check==1):
        count+=1
count=count%(10**9+7)
print(count)

Submission status: Runtime Error

Solution code:
import copy
S = input()
N = len(S)

S2 = []
for k in range(N):
    S2.append(S[k])

T = copy.copy(S2)
for i in range(N):
    if T[i] == "?":
        T[i] = "9"

T2 = ''.join(T)

T2 = int(T2)
M = T2//13 #整数部分

ans = 0

for j in range(M):
    S3 = copy.copy(S2)
    Q = 13*j+5 #比較
    Q = str(Q)
    q = len(Q)
    Q2 = [0 for u in range(N)]
    for p in range(q):
        Q2[-p-1] = Q[-p-1]
    
    
    for i in range(N):
        if S3[i] == "?":
            S3[i] = Q2[i]
        print(S3)
    
    if S3 == Q2:
        ans += 1

ans = ans%(10**9+7)

print(ans)

Submission status: Runtime Error

Solution code:
S = input()
T = []
mod = int(10**9+7)

for k in range(6):
    T.append([])
    r = 10**k
    for j in range(10):
	T[-1].append(j*r%13)

dp = [1]+[0]*12
k = (len(S)-1)%6
for s in S:
    dp_new = [0]*13
    if s=='?':
        tt = T[k]
        for r in range(10):
            m = tt[r]
            for i, dd in enumerate(dp):
                dp_new[(i+m)%13] += dd
    else:
        m = T[k][int(s)]
        for i in range(13):
            dp_new[(i+m)%13] = dp[i]
    dp = [d%mod for d in dp_new]
    k=(k+5)%6

print(dp[5]%mod)

Submission status: Runtime Error

Solution code:
s = input()
S = []
q = []
for i in range(len(s)):
        if s[i] == '?':
                S.append(-1)
                q.append(i)
        else: S.append(int(s[i]))

mod = []
for i in range(len(S)):
        if S[i] == -1: mod.append(pow(10,len(S)-i-1,13))
m = 0
for i in range(len(S)):
        if S[i] >= 0:
                m += pow(10,len(S)-i-1,13) * S[i]
                m = (m%13)
#print(mod)
#print(s)
c = 0
for i in range(pow(10,len(q))):
        s = str(0) * (len(q)-len(str(i))) + str(i)
        l = 0
        for j in range(len(s)): l += (int(s[j]) * mod[j])
        if (l+m)%13 == 5: c += 1
print(c%(pow(10,9)+7))

Submission status: Runtime Error

Solution code:
S = input()

ans = 0
q = [S]
while q:
    s = q.pop()
    if '?' not in s:
        if int(s) % 13 == 5:
            ans += 1
    else:
        for i in range(10):
            q.append(s.replace('?', str(i), 1))

print(ans)

Submission status: Runtime Error

Solution code:
import math
import re

S=input()

MAX=int(S.replace('?','9'))-5
MIN=int(S.replace('?','0'))-5
MAX13=int(MAX/13)*13
MIN13=math.ceil(MIN/13)*13
s=S.replace('?','.')

cnt=0
for n in range(MIN13,MAX13+1,13):
    if re.match(s,str(n+5).zfill(len(S))):
        cnt+=1

print(cnt % 1000000007)

Submission status: Runtime Error

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

a = 130
for i in range(100000);
    b = a % 13

print(a)

Submission status: Runtime Error

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

a = 130
for i in range(100000)
    b = a % 13

print(a)

Submission status: Runtime Error

Solution code:
S = input()
N = len(S)
su = 0
L = [0]*13
L[0] = 1
M = [1, 10, 9, 12, 3, 4]
mod = 10**9+7
for i, c in enumerate(S[::-1]):
    m = M[i % 6]
    if c=="?":
        Lc = L.copy()
        for j in range(m, m*10, m):
            for k in range(13):
                idx = (k+j)%13
                L[idx] = (L[idx] + Lc[k]) % mod
    else:
        su += int(c) * m
print(L[(-su+5)%13])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

MOD = 10 ** 9 + 7
s = input().strip()
if s[-1] == "?":
    tmp = [1 for i in range(10)] + [0 for i in range(3)]

else:
    tmp = [0 for i in range(13)]
    # print("-------------------")
    # print(s[-1])
    # print(int(s[-1]))
    tmp[int(s[-1])] = 1

keta = 1
for c in s[::-1][1:]:
    keta  = (keta * 10) % 13
    nw = [0 for i in range(13)]
    if c != "?":
        seni = int(c) * keta
        for j, num in enumerate(tmp):
            nw[(j+seni)%13] += num
    else:
        for isure in range(10):
            seni = int(isure) * keta
            for j, num in enumerate(tmp):
                nw[(j + seni) % 13] += num
    # print(nw)
    tmp = [num % MOD for num in nw]
    # tmp = nw
print(nw[5] % MOD)