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:
mod=10**9+7
s=input()

b=int(s.replace("?","0"))%13
if b<=5:
    cal=5-b
else:
    cal=18-b
d=[0 for _ in range(13)]
p=[[i*j%13 for i in range(10)] for j in range(13)]
rev=s[::-1]
num=rev.find("?")
if num==-1:
    if cal==0:
        print(1)
    else:
        print(0)
else:
    tmp=10**(i+num+1)%13
    for i in p[tmp]:
        d[i]+=1
    c=rev[num+1:]
    for i,v in enumerate(c):
        #print(i+num+1)
        if v=="?":
            tmp=10**i%13
            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[(p[tmp][j]+k)%13]+=d[k]
                #print(t_d)
            #for j in range(13):
                #d[j]=t_d[j]
            d=t_d
            #print(t_d)
    #print(d)
    print(d[cal]%mod)

Submission status: Runtime Error

Solution code:
s = input()
dp = [[0 for i in range(13)] for i in range(len(s))]
if s[-1] != "?":
    r_0 = int(s[-1]) % 13
    dp[0][r_0] += 1
else:
    for k in range(10):
        r_0 = k % 13
        dp[0][r] += 1

for i in range(1,len(s)):
    for r in range(13):
        if s[-(i+1)] != "?":
            j = (int(s[-(i+1)]) * (10**i) + r) % 13
            dp[i][j] += dp[i-1][r]
        else:
            for k in range(10):
                j = (k * (10**i) + r) % 13
                dp[i][j] += dp[i-1][r]
print(dp[len(s)-1][5]%(10**9+7))

Submission status: Runtime Error

Solution code:
s = input()
dp = [[0 for i in range(13)] for i in range(len(s))]
r_0 = int(s[-1]) % 13
dp[0][r_0] = 1

for i in range(1,len(s)):
    for r in range(13):
        if s[-(i+1)] != "?":
            j = (int(s[-(i+1)]) * (10**i) + r) % 13
            dp[i][j] += dp[i-1][r]
        else:
            for k in range(10):
                j = (k * (10**i) + r) % 13
                dp[i][j] += dp[i-1][r]
print(dp[len(s)-1][5]%(10**9+7))

Submission status: Runtime Error

Solution code:
S=input()
# S = "??2??5"
# S= "?44"

MOD = 10**9+7
dp = {}
for i in range(13):
    dp[(-1,i)] = 0
dp[(-1,0)] = 1
for t,ss in enumerate(S[::-1]):
    for i in range(13):
        dp[(t,i)] = 0
    if ss=="?":
        for i in range(13):
            for j in range(10):
                dp[(t,(j*10**t+i)%13)] += dp[(t-1,i)]
                dp[(t,(j*10**t+i)%13)] %= MOD
    else:
        s = int(ss)
        for i in range(13):
            dp[(t,(s*10**t+i)%13)] += dp[(t-1,i)]
            dp[(t,(j*10**t+i)%13)] %= MOD


print(dp[(t,5)])

Submission status: Runtime Error

Solution code:
S = input()
l = len(S)
S2 = []
S3 = []
idx = 0
for i in range(l):
  if(S[i] != '?'):
    idx = i
    break

for i in range(l):
  if (S[i] != '?'):
    S2.append(S[i])
  else:
    S2.append('9')
    
for i in S[idx:]:
  if (i != '?'):
    S3.append(i)
  else:
    S3.append('0')
max = int(''.join(S2))
min = int(''.join(S3))

ans = 0

a = min + (5 - (min % 13))
b = max + (5 - (min % 13))
print((int((b-a) / 13) + 1)  % ((10 ** 9) + 7))

Submission status: Runtime Error

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

b=int(s.replace("?","0"))%13
if b<=5:
    cal=5-b
else:
    cal=18-b

p=[[i*j%13 for i in range(10)] for j in range(13)]
rev=s[::-1]
d={i:0 for i in range(13)}
num=rev.find("?")
tmp=10**num%13
for i in p[tmp]:
    d[i]+=1

for i,v in enumerate(rev[num+1:]):
    #print(i+num+1)
    if v=="?":
        tmp=10**(i+num+1)%13
        t_d={i:0 for i in range(13)}
        #print("i,tmp:",i+num+1,",",tmp)
        for k in range(0,13):
            for j in range(0,10):
                t_d[(p[tmp][j]+k)%13]+=d[k]
            #print(t_d.values())
        for j in range(13):
            d[j]=t_d[j]
        #print(t_d)
#print(d)
print(d[cal]%mod)

Submission status: Runtime Error

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

import sys

s= sys.stdin.readline()
#
m0 = 0
mmap= []
for i in range(6):
    b = 10**i % 13
    mmap.append( [ (b*i)%13 for i in range(10) ] )
#
dp= [ 0 for i in range(13) ]
for i,c in enumerate(reversed(s)):
    tmp  = dp.copy()
    if i==0: tmp[0]= 1
    #
    if c=="?":
        bset = mmap[i%6][1:]
        for m in range(13):
            num= tmp[m]
            if num==0: continue
            for b in bset:
                idx= (m+b)%13
                dp[idx]+= num
    else:
        b= mmap[i%6][int(c)]
        for m in range(13):
            idx= (m+b)%13
            dp[idx]= tmp[m]
#
print(dp[5])

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    S = SI()
    #S = S[::-1]
    N = len(S)
    dp = [[0 for j in range(13)] for i in range(N)]
 
    for i in range(N,0,-1):
        c = S[i]
        if i == 0:
            if c == '?':
                for j in range(10):
                    dp[i][j] = 1
            else:
                dp[i][int(c)] = 1
        else:
            for k in range(13):
                if c == '?':
                    for j in range(10):
                        amari = (j * pow(10, i, 13))
                        dp[i][k] = (dp[i][k] + dp[i-1][(k-amari)%13]) % MOD
                else:
                    amari = (int(c) * pow(10, i, 13))
                    dp[i][k] += (dp[i][k] + dp[i-1][(k-amari) % 13]) % MOD
 
    dprint(dp)
    print(dp[N-1][5])

solve()

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
from collections import deque
import itertools
from itertools import permutations
import sys
import bisect
sys.setrecursionlimit(10**6)
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
YNeos='YNeos'
mo=10**9+7
imp='IMPOSSIBLE'

input=sys.stdin.readline
s=input()
t=list(s)[::-1]
ans=0
dp=[0]*13
dp[0]=1
for d in range(len(t)):
    
    if t[d]=='?':
        tm=[0]*13
        for x in range(10):
            r=int(x)*(10**d)
            for i in range(13):
                tm[(i+r)%13]+=dp[i]
        dp=[j%mo for j in tm]
    else:
        tm=[0]*13
        r=int(t[d])*(10**d)
        for i in range(13):
            tm[(i+r)%13]=dp[i]
        dp=[j for j in tm]

print(dp[5]%mo)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
from collections import deque
import itertools
from itertools import permutations
import sys
import bisect
sys.setrecursionlimit(10**6)
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
YNeos='YNeos'
mo=10**9+7
imp='IMPOSSIBLE'

input=sys.stdin.readline
s=input()
t=list(s)[::-1]
ans=0
dp=[0]*13
dp[0]=1
for d in range(len(t)):
    
    if t[d]=='?':
        tm=[0]*13
        for x in range(10):
            r=int(x)*(10**d)
            for i in range(13):
                tm[(i+r)%13]+=dp[i]
        dp=[j%mo for j in tm]
    else:
        tm=[0]*13
        r=int(t[d])*(10**d)
        for i in range(13):
            tm[(i+r)%13]=dp[i]
        dp=[j for j in tm]
    #print(dp)

print(dp[5]%mo)

Submission status: Runtime Error

Solution code:
def main():
  mod = 10**9+7 
  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 j in range(10):
        num = int(j*(10**(n-i-1)))%13
        #print(j,num,np.roll(ans,num))
        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]%mod for i in range(len(tmp))]
      
      
  #print(ans)
  print(ans[5])
 

if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
S = input()
a = 10**9+7

f = S.count("?")
count = 1
c = 0
for i in range(f):
    c +=  9 * count
    count = 10**(i+1)

b = (c-5)//13
for i in range(len(S)):
  if S[i] == "?":
    first = i
    break

for i in range(0,10):
  Sr = S.replace("?","9")
  Sr = Sr[:first] + str(i) + Sr[first:]
  Sl = int(Sr)
  if Sl%13 == 5:
    b += 1
    
print(b%a)

Submission status: Runtime Error

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

MOD = pow(10, 9) + 7

def main():
  s = input().strip()
  sd = [[0 for _ in range(13)] for _ in range(len(s))]
  if s[-1] == '?':
    for i in range(10):
      sd[0]]i] = 1
  else:
    sd[0][int(s[-1])] = 1

  for i, _s in enumerate(s[::-1]):
    if i == 0:
      continue
    if _s != '?':
      rem = int(_s) * pow(10, i, 13) % 13
      for j in range(13):
        sd[i][(j+rem)%13] = sd[i-1][j]
    else:
      for k in range(10):
        rem = k * pow(10, i, 13) % 13
        for j in range(13):
          sd[i][(j+rem)%13] += sd[i-1][j]
          sd[i][(j+rem)%13] %= MOD
  print(sd[5])


if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
s = input()
 
s = s[::-1]
 
dp = [0 for _ in range(13)]
 
if s[0] == '?':
    for j in range(10):
        dp[j] = 1
else:
    dp[int(s[0])] = 1

m = 1
MOD = 10**9 +7
 
s = s[1:]

for w in s:
    m = m*10 % 13
    ans = [0 for _ in range(13)]
 
    if w == '?':
        for k in range(13):
            for j in range(10):
                ans[(j*m+k)%13] += dp[k]
                ans[k] % MOD
    else:
        for k in range(13):
            ans[(int(w)*m + k) %13] += dp[k]
            ans[k] % MOD
    for k in range(13):
        dp[k] = ans[k]
        ans[k] = ans[k] % MOD
 
print(ans[5] % MOD )

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

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

dp=[[0 for j in range(13)] for i in range(len(a))]
for i in range(len(a)):
  if 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])

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:
MOD = 10 ** 9 + 7
def add(a, b):
  return (a + b) % MOD
def sub(a, b):
  return (a - b) % MOD
def mul(a, b):
  return ((a % MOD) * (b % MOD)) % MOD
def div(a, b):
  return ( (a % MOD) * (power(b, MOD)) ) % MOD
def power(a, b):
  return pow(a, b, MOD)


def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
  
N = 2000
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % MOD )
    inverse.append( ( -inverse[MOD % i] * (MOD//i) ) % MOD )
    g2.append( (g2[-1] * inverse[-1]) % MOD )

s = input()
n = len(s)
q = []
a = []
for c in s:
  if c == '?':
    q.append(n-i-1)
  else:
    a.append([n-i-1, int(c)])

def match(x, a_):
  for s, t in a_:
    if (x // (10 ** s)) % 10 != t:
      return False
    return True

cnt = 0
x = 5 - 13
while True:
  if x > 10 ** n:
    break
  x += 13
  if match(x, a):
    cnt = add(cnt, 1)
  
return cnt

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7
def add(a, b):
  return (a + b) % MOD
def sub(a, b):
  return (a - b) % MOD
def mul(a, b):
  return ((a % MOD) * (b % MOD)) % MOD
def div(a, b):
  return ( (a % MOD) * (power(b, MOD)) ) % MOD
def power(a, b):
  return pow(a, b, MOD)


def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
  
N = 2000
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % MOD )
    inverse.append( ( -inverse[MOD % i] * (MOD//i) ) % MOD )
    g2.append( (g2[-1] * inverse[-1]) % MOD )

s = input()
n = len(s)
q = []
a = []
for c in s:
  if c == '?':
    q.append(n-i-1)
  else:
    a.append([n-i-1, int(c)])

def match(x, a_):
  for s, t in a_:
    if (x // (10 ** s)) % 10 != t:
      return False
    return True

cnt = 0
x = 5 - 13
while True:
  if x > 10 ** n:
    break
  x += 13
  if match(x, a)
      cnt = add(cnt, 1)
  
return cnt

Submission status: Runtime Error

Solution code:

N = input()

big = N.replace("?","9")
big_n = int(big)

divi = int(big_n / 13)
addd = int(big_n % 13)

count = 0

if addd > 4:
    count = divi + 1
else:
    count = divi


rev_N = N[::-1]
print(rev_N)


for i in range(len(N)):
    if i == 0:
        continue
    if rev_N[i] == "?":
        continue
    else:
        X = rev_N[:i+1].replace("?","9")
        X2 = X[::-1]
        X_num = int(X2)

        diviv = int(X_num/13)
        adidi = int(X_num % 13)

        if adidi > 4:
            count -= divi + 1
        else:
            count -= divi




print(count % (pow(10,9)+7))

# count = 0
#
# for i in range(len(N)):
#     if i == 0:
#         continue
#     else:
#         X_num = int(X[-i-1:])
#         # print(X_num)
#         div = int(X_num/13)
#         amari = X_num % 13
#
#         if amari > 4:






# print(X[-3])

Submission status: Runtime Error

Solution code:
import copy

rest = 10**9 + 7
s = input()
n = len(s)
min_num = s.replace('?','0')
min_list = list(map(int, min_num))
min_num = int(min_num)

cnt = 0
x = 10**n - 1
num_index = []
x_index = []

for i in range(-1,-(n+1),-1) :
  if s[i] != '?' :
    num_index.append(i)
  else :
    x_index.append(i)

# print(num_index)
# for i in range(1,len(x_index)+1) :
#   if min_num % 13 == 5 :
#     break
#   else :

flag = False
for i in list(range(18,10**n-1,13)) :
  q = str(i)
  if len(q) < abs(num_index[-1]) :
    continue
  
  for j in num_index :
    if q[j] == s[j] :
      continue
    else :
      flag = True
      break
  
  if flag :
    flag = False
    continue
  cnt += 1

print(cnt%rest)

# for i in list(range(18,1000000,13)) :
#   q = str(i)
#   if len(q) < 4 :
#     continue
#   else :
#     if q[-4] == '2' and q[-1] == '5' :
#       cnt += 1
#       print(q)
# print(cnt)

Submission status: Runtime Error

Solution code:
S = input()
N = len(S)
count = [0, 0, 0, 0, 0, 0]
mod = [1, -3, -4, -1, 3, 4]
m = 0
for i in range(N):
    if(S[N-i-1] == '?'):
        count[i % 6] += 1
    else:
        m += mod[i % 6] * int(S[N-i-1])
        m %= 13

M = 10**9 + 7
print(sum(count))

if(sum(count) == 0):
    print(0)
    exit()


def func(power):
    x = 10 ** power % M
    return x // 13
    
    
    
c_min = 13
remain_list = [0, 0, 0, 0, 0, 0]
power = 1
for i in range(6):
    if(count[i] == 0):
        continue
    else:
        remain = count[i] % 13
        power *=  (count[i] - remain)
        remain_list[i] = remain 

c = 0
for i in range(len(remain[0])):
    for j in range(len(remain[1])):
        for k in range(len(remain[2])):
            for l in range(len(remain[3])):
                for m in range(len(remain[4])):
                    for n in range(len(remain[5])):
    if i * mod[0] + j * mod[1] + k * mod[2] + l * mod[3] + m * mod[4] + n * mod[5] % 13 == 0:
        c += 1
                        
    
print(func(power) + c)

Submission status: Runtime Error

Solution code:
import math


def solve():
    S = input()
    q_count = S.count('?')
    ans = math.ceil(10 ** q_count / 13)
    if int(S.replace('?', '0')) % 13 != 0:
        ans -= 1
    if int(S.replace('?', '9')) % 13 != 0:
        ans -= 1
    if ans < 0:
        print(0)
    else:
        print(ans % (10 ** 9 + 7))


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
S = input()
a = 10**9+7

f = S.count("?")
count = 1
c = 0
for i in range(f):
    c +=  9 * count
    count += 10*(i+1)

b = ((c-5)//13*13)/13
for i in range(len(S)-1,0,-1):
  if S[i] == "?":
    last = i
    break
  
for i in range(0,10):
  Sr = S.replace("?","0")
  Sr = Sr[:last] + str(i) + Sr[last:]
  print(Sr)
  Sl = int(Sr)
  if Sl%13 == 5:
    c += 1
    
print(c%a)

Submission status: Runtime Error

Solution code:
S = input()
 
dp = [[0]*13 for j in range(len(S)+1)]
mod = 10**9+7
 
dp[0][0] = 1
k = 1
L0 = list(range(10))

for s in S:
  if ('?' == s):
    L = L0
  else:
    L = [int(s)]
 
  for l in L:
    for i in range(13):
      tmp = (i * 10) + l
      m = tmp % 13
      dp[k][m] = ((dp[k][m][0] + dp[k-1][i][0]) % mod)
  k += 1
print(dp[k-1][5])

Submission status: Runtime Error

Solution code:

s = input()

v_zero = int(s.replace('?','0'))

c = [0,0,0,0,0,0]
modu = [1,10,9,12,3,4]
d = 0
for i in range(len(s)):
	if (s[i] == '?'):
		c[(len(s)-i-1)] +=1
	else:
		d += int(s[i]) * 10**(len(s)-i-1)

d %= 13
n=0
for c0 in range(10 * c[0] + 1):for c1 in range(10 * c[1] + 1):for c2 in range(10 * c[2] + 1):for c3 in range(10 * c[3] + 1):for c4 in range(10 * c[4] + 1):for c5 in range(10 * c[5] + 1):
	if((c0*modu[0]+c1*modu[1]+c2*modu[2]+c3*modu[3]+c4*modu[4]+c5*modu[5]+d) % 13 == 5):n +=1
print(n)

Submission status: Runtime Error

Solution code:
s = list(input())

digits = len(s)
s.reverse()
dp = [ [0] * 13 for i in range(digits)]
# dp[i][j] は i+1桁目までで13で割った余りがjのものを格納する

for i in range(digits):
    if s[i] == '?':
        for j in range(10):
            if i == 0:
                dp[i][j] += 1
            else:
                amari = ( j * 10 ** (i) ) % 13
                for k in range(13):
                    dp[i][(k+amari)%13] += dp[i-1][k]
    else:
        val = int(s[i])
        if i == 0:
            dp[i][val] += 1
        else:
            amari = ( val * 10 ** (i) ) % 13
            for k in range(13):
                dp[i][(k+amari)%13] += dp[i-1][k]
    
print(dp[digits-1][5]/(10**9 + 7))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(4100000)

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)

import re

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

    logger.debug(S)
    p = re.compile(r'\?')
    q_index_list = [m.span()[0] for m in p.finditer(S)]
    logger.debug(q_index_list)

    new_s_list = list(S)
    for i in q_index_list:
        new_s_list[i] = '0'

    zero_s = int(''.join(new_s_list))

    r = (5 - (zero_s % 13)) % 13

    old_count_dict = dict(zip(range(13), [0]*13))
    old_count_dict[r] = 1

    for i in q_index_list:
        order = len(S) - i - 1

        order_mod = order % 13

        new_count_dict = dict(zip(range(13), [0]*13))

        for j in range(10):
            x = (order_mod * j) % 13
            for k in range(13):
                r = k - x
                new_count_dict[r] += old_count_dict[k]
        
        old_count_dict = new_count_dict

    print(old_count_dict[0] % (10**9 + 7))






if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

Submission status: Runtime Error

Solution code:
import math

s = list(input())
# print(s)
count = 0
hatena = 1

for i in len(s):
    if(s[i] == '?'):
        hatena *= 10

keta = math.log10(hatena)

for i in range(hatena):
    subs = s
    subketa = keta
    for j in s:
        if(subs[j] == '?'):
            subs[j] = (i // 10**(subketa-1)) % 10
    for j in s:
        num = subs[j]
        num *= 10
    num //= 10
    if(num % 13 == 5):
        count += 1

print(count % 1000000007)

Submission status: Runtime Error

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

mod = 1
stable = 0
calc = {i: 0 for i in range(13)}
for c in reversed(s):
    if c == '?':
        calc[mod] += 1
    else:
        stable = (int(c) * mod + stable) % 13
    mod = (mod * 10) % 13

value = stable % 13

DIV = 10**9 + 7

# combis = {}
# def combi(n, r):
#     if r == 0:
#         return 1
#     elif (n, r) in combis:
#         return combis[n, r]
#     else:
#         res = combi(n, r - 1) * (n + 1 - r) // r
#         combis[n, r] = res
#         return res

patterns = {}
def get_pattern(d, n):
    if n == 0 or d * 9 == n:
        return 1
    elif d * 9 < n:
        return 0
    elif d == 1:
        return 1
    elif (d, n) in patterns:
        return patterns[d, n]
    else:
        res = 0
        for i in range(1, d):
            for j in range(9 * d + 1):
                res = get_pattern(i, j) * get_pattern(d-i, n-j)
        patterns[d, n] = res % DIV
        return res

def get_chance(point, value, chance):
    if point == 13:
        if value == 5:
            pat = 1
            for pt, val in enumerate(chance):
                pt += 1
                pat = (pat * get_pattern(calc[pt], val)) % DIV
            return pat
        else:
            return 0
    res = 0
    if calc[point] == 0:
        res = get_chance(point + 1, value, chance + [0])
    else:
        for i in range(calc[point] * 9 + 1):
            res += get_chance(point + 1, (value + i * point) % 13, chance + [i])
    return res

result = get_chance(1, value, [])

print(result)

Submission status: Runtime Error

Solution code:
s=input()[::-1]
pos=[i for i,v in enumerate(s) if v=="?"]
pos=[[10**i*j%13 for j in range(10)] for i in pos]
remainder=0
count=0
for i in range(len(s)):
    if not s[i]=="?":
        remainder=(remainder+((10**i*int(s[i]))%13))%13
def iterate(array):
    for i in array[0]:
        if array[1:]:
            for j in iterate(array[1:]):
                yield (i+j)%13
        else:
            yield i%13
count=list(iterate(pos))
count=[i for i in count if i==5]
count=len(count)
print(count%(10**9+7))

Submission status: Runtime Error

Solution code:
S = input()
i = 0
length = len(S)
head = 0 
head_num = 0
number = []
for i, s in enumerate(list(S)):
    if s != "?":
        number.append([i,s])

head_num = length - number[0][0]
x_min = ["0"] * length
for num in number:
    x_min[num[0]] = num[1]
if number == []:
    x_min = 0
else:
    x_min = x_min[number[0][0]:]
    x_min = int("".join(x_min))


k = x_min // 13 +1

if x_min > 13 * k + 5:
    k += 1

if number[0][0] ==0:
    x_max = (number[0][1]+1) * (10**(length-1))
else:
    x_max = 10 **(length)


ans =0
while True:
    x = str(13*k +5)
    if 13*k +5 >= x_max:
        break
    d = length - len(x)
    for i , num in enumerate(number):
        if str(x)[num[0]-d] != num[1]:
            break
        if i == len(number)-1:
            ans += 1
    k += 1
print(int(ans%(10e9 +7)))

Submission status: Runtime Error

Solution code:
s = input()
 
s = s[::-1]
 
dp = [0 for _ in range(13)]
 
if s[0] == '?':
    for j in range(10):
        dp[j] = 1
else:
    dp[int(s[0])] = 1
m = 1
MOD = 10**9 +7
 
for i in range(1,len(s)):
    m = m*10 % 13
    ans = [0 for _ in range(13)]
 
    if s[i] == '?':
        for k in range(13):
            for j in range(10):
                ans[(j*m+k)%13] += dp[k]
                ans[k] % MOD
    else:
        for k in range(13):
            ans[(int(s[i])*m + k) %13] += dp[k]
            ans[k] % MOD
    for k in range(13):
        dp[k] = ans[k]
        ans[k] = ans[k] % MOD

print(ans[5] % MOD )

Submission status: Runtime Error

Solution code:
def f(num, i, n):
    r = 0
    if i >= n:
        r += 1 if (int(num)%13)==5 else 0
    elif num[i] == '?':
        m0 = "" if i == 0 else num[0:i]
        for j in range(10):
            m1 = str(j)
            m2 = num[i+1:]
            r += f(m0+m1+m2, i+1, n)
    else:
        r += f(num, i+1, n)
    return(r % (10**9+7))

s=input()
print(f(s, 0, len(s)))

Submission status: Runtime Error

Solution code:
#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vll = vector<ll>;
using vii = vector<int>;
using pii = pair<int, int>;
template <typename T = vii>
using vec = vector<T>;

const ll INF = 1e18, MOD = 1e9 + 7;

const int MAX = 1e6;

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    // freopen("in.in", "r", stdin);

    string s;
    cin >> s;
    const int n = s.size();
    vii a;
    int val = 0;
    for (int p = 1, i = n - 1; i >= 0; i--, (p *= 10) %= 13) {
        if (s[i] == '?') {
            a.push_back(p);
        }
        else {
            (val += p * (s[i] - '0')) %= 13;
        }
    }
    val = (5 - val + 13) % 13;
    vll dp(13);
    dp[0] = 1;
    for (int x : a) {
        vll new_dp(13);
        for (int i = 0; i < 13; i++) {
            for (int j = 0; j < 10; j++) {
                const int k = (i + j * x) % 13;
                (new_dp[k] += dp[i]) %= MOD;
            }
        }
        swap(dp, new_dp);
    }
    cout << dp[val] << '\n';
}

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
mod = 1e+9+7
s = input()
print(int((10**s.count('?')//13)%mod))

Submission status: Runtime Error

Solution code:
s=input()[::-1]
pos=[i for i,v in enumerate(s) if v=="?"]
pos=[10**i*j%13 for j in range(10)] for i in pos]
remainder=0
count=0
for i in range(len(s)):
    if not s[i]=="?":
        remainder=(remainder+((10**i*int(s[i]))%13))%13
def iterate(array):
    for i in array[0]:
        if array[1:]:
            for j in iterate(array[1:]):
                yield (i+j)%13
        else:
            yield i%13
count=list(iterate(pos))
count=[i for i in count if i==5]
count=len(count)
print(count%(10**9+7))

Submission status: Runtime Error

Solution code:
import math
S=input()
hatena = S.count("?")
S_temp = int(S.replace("?","0"))
Q = 10 ** hatena
S_temp_amari =(S_temp-5) %13
temp = math.floor((Q-S_temp_amari)/13)
print(temp%(1000000000+7))

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) + "}"

cnt = 0
for i in range(start,N+1):
    can = tmp.format(13*i + 5) 
    for i, (a,b) in enumerate(zip(list(can), 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:
mod = 1e+9+7
s = input()
print(int(((10**s.count('?')-5)//13)%mod))

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

Submission status: Runtime Error

Solution code:
S = str(input())
mod = 10**9 + 7
odd = ""
oddCnt = [0,0,0]
oddSum = 0
even = ""
evenCnt = [0,0,0]
evenSum = 0
for i in range(len(S)//3):
    for j in reversed(range(3)):
        if S[i+j] == "?":
            if i%2 == 0:
                odd += "0"
                oddCnt[j] += 1
            else:
                even += "0"
                evenCnt[j] += 1
        else:
            if i%2 == 0:
                odd += S[i+j]
            else:
                even += S[i+j]
    if odd != "":
        oddSum += int(odd)
    if even != "":
        evenSum += int(even)
    odd = ""
    even = ""
if len(S)%3 != 0 and (len(S)//3 + 1)%2 == 1:
    for j in reversed(range(len(s)%3)):
        if S[(len(s)//3) * 3+j] == "?":
            odd += "0"
            oddCnt[j] += 1
        else:
            odd += S[(len(s)//3) * 3+j]
    oddSum += int(odd)
elif len(S)%3 != 0 and (len(S)//3 + 1)%2 == 0:
    for j in reversed(range(len(s)%3)):
        if S[(len(s)//3) * 3+j] == "?":
            even += "0"
            evenCnt += 1
        else:
            even += S[(len(s)//3) * 3+j]
    evenSum += int(even)
tmpL = oddSum - evenSum + (oddCnt[2]+evenCnt[2])*900 + (oddCnt[1]+evenCnt[1])*90 + (oddCnt[0]+evenCnt[0])*9
tmpS = oddSum - evenSum - (oddCnt[2]+evenCnt[2])*900 + (oddCnt[1]+evenCnt[1])*90 + (oddCnt[0]+evenCnt[0])*9
print(((tmpL-5)//13 - (tmpS-6)//13)%mod)