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:
P = 10**9+7
Q = 13

dp = [0 for _ in range(Q)]
dp_pre = [0 for _ in range(Q)]

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

for i in range(1, len(S)):
    for k in range(Q):
        dp_pre[k] = dp[k]
        dp[k] = 0

    if S[i] == '?':
        for j in range(10): # 数字
            for k in range(Q): # 前の配列
                q = (j+10*k)%Q
                dp[q] += dp_pre[k]
    else:
        for k in range(Q):
            q = (int(S[i])+10*k)%Q
            dp[q] += dp_pre[k]

    for k in range(Q):
        dp[k] = dp[k] % P

ans = dp[5] % P
print(ans)

Submission status: Runtime Error

Solution code:
S = input()

# 桁数
N = len(S)
MOD = 10**9 + 7

# dp[i][j] := Sの上からi桁目までを考えた時、それを13で割った余りがjになる方法の数
dp = [[0 for _ in range(13)]for _ in range(N + 1)]

# １桁目について
if S[0] == "?":
    # ?に0, 1, ..., 9を入れることができる
    for i in range(10):
        dp[1][i] = 1
else:
    dp[1][S[0]] = 1

# 1, 2, ..., N-1桁から、
# 2, 3, ..., N桁についての遷移を考える
for i in range(1, N):
    for j in range(13):
        if S[i] == "?":
            for k in range(10):
                dp[i + 1][(j * 10 + k) % 13] += dp[i][j]
                dp[i + 1][(j * 10 + k) % 13] %= MOD
        else:
            dp[i + 1][(j * 10 + int(S[i])) % 13] += dp[i][j]
            dp[i + 1][(j * 10 + int(S[i])) % 13] %= MOD

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

Submission status: Runtime Error

Solution code:
import numpy as np

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

l = len(S)

dp = np.zeros((l + 1, 13))

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

dp[0][0] = 1

for i, num in enumerate(S):

    if num == "?":
        for k in range(10):
            for j in range(13):
                dp[i+1][((j * 10) + k) % 13] += dp[i][j]
                # nextdp[((j * 10) + k) % 13] %= mod

    else:
        k = int(num)
        for j in range(13):
            dp[i+1][((j * 10) + k) % 13] += dp[i][j]
            # nextdp[((j * 10) + k) % 13] %= mod

    for j in range(13):
        dp[i+1][j] %= mod

print(int(dp[l][5]))

Submission status: Runtime Error

Solution code:
s = list(input())

digit = []
num = []

for i in s:
  if i != '?':
    digit.append(len(s) - s.index(i))
    num.append(int(i))

cnt = 0

m = sum(num[i]*(10**(digit[i]-1)) for i in range(len(digit)))
m13 = (m-5) // 13

M = 10**len(s)
M13 = (M-6) //13

for i in range(m13, M13+1):
  x = str(13*i + 5)
  x = [int(i) for i in x]
  x.reverse()
  for j in range(len(digit)):
    if x[digit[j] - 1] != num[j]:
      break
    if j == len(digit) - 1:
      cnt += 1

print(cnt)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

S = input().strip()

MOD = 10 ** 9 + 7

lens = len(S)

sys.setrecursionlimit(10 ** 8)

@lru_cache(maxsize=None)
def solve(amari, keta):
    if keta == lens - 1:
        if S[keta] == "?":
            cnt = 0
            for i in range(9, -1, -1):
                if (amari + i) % 13 == 5:
                    cnt += 1
            return cnt
        else:
            if (amari + int(S[keta])) % 13 == 5:
                return 1 % MOD
            else:
                return 0
    else:
        if S[keta] == "?":
            x = 0
            for i in range(9, -1, -1):
                x += solve((amari + (i * 10 ** (lens - 1 - keta)) % 13) % 13, keta + 1)
            return x % MOD
        else:
            return solve((amari + (int(S[keta]) * 10 ** (lens - 1 - keta)) % 13) % 13, keta + 1) % MOD


print(solve(0, 0) % MOD)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

S = input().strip()

MOD = 10 ** 9 + 7

lens = len(S)


@lru_cache(maxsize=None)
def solve(amari, keta):
        if keta == lens - 1:
            if S[keta] == "?":
                cnt = 0
                for i in range(9, -1, -1):
                    if (amari + i) % 13 == 5:
                        cnt += 1
                return cnt
            else:
                if (amari + int(S[keta])) % 13 == 5:
                    return 1
                else:
                    return 0
        else:
            if S[keta] == "?":
                x = 0
                for i in range(9, -1, -1):
                    x += solve((amari + (i * 10 ** (lens - 1 - keta)) % 13) % 13, keta + 1)
                return x % MOD
            else:
                return solve((amari + (int(S[keta]) * 10 ** (lens - 1 - keta)) % 13) % 13, keta + 1) % MOD


print(solve(0, 0) % MOD)

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict

S=input()[::-1]
mod=10**9+7

rlist={}
for n in [1,10,9,12,3,4]:
  rlist[n] = [i*n%13 for i in range(13)]

count=defaultdict(int)
SUM=0
for i in range(len(S)):
  if S[i]!='?':SUM+= pow(10,i,13)*int(S[i])
  else:
    r = i % 6
    if r == 0:count[1]+=1
    elif r == 1:count[10]+=1
    elif r == 2:count[9]+=1
    elif r==3:count[12]+=1
    elif r==4:count[3]+=1
    elif r==5:count[4]+=1
SUM %= 13

keys=list(count.keys())

for k in keys:
  count[k] %= mod

table=[[0 for i in range(len(keys))] for j in range(13)]
for j,k in enumerate(keys):
  q,r = divmod(count[k]*10,13)
  for i in range(13):
    if i+1<=r:
      table[rlist[k][i]][j]+=(q+1)
    else:
      table[rlist[k][i]][j]+=q

total = [[0 for i in range(len(keys))] for j in range(13)]
for i in range(len(keys)):
  for j in range(13):
    if i == 0:
      total[j][i] = table[j][i]
      continue
    for k in range(13):
      total[(j+k)%13][i] += total[j][i-1]*table[k][i]%mod
      
print(total[(5-SUM)%13][-1]%mod)

Submission status: Runtime Error

Solution code:
def readinput():
    s=input()
    return s

def printTbl(tbl):
    for l in tbl:
        print(l)

def main(s):
    MOD=10**9+7

    Rtbl=[]
    for _ in range(10):
        Rtbl.append([0]*13)
    for i in range(1,10):
        for j in range(13):
            Rtbl[i][j]=(Rtbl[i-1][j]+j)%13
    #printTbl(Rtbl)

    n=len(s)
    p0=0
    q=[]
    for i in range(n):
        if s[i]!='?':
            p0=(p0*10+int(s[i]))%13
            for j in range(len(q)):
                q[j]=(q[j]*10)%13
        else:
            p0=(p0*10)%13
            for j in range(len(q)):
                q[j]=(q[j]*10)%13
            q.append(1)
    #print(p0,q)

    nq=len(q)
    Ptbl=[]
    for _ in range(13):
        Ptbl.append([0]*nq)
    q0=q[0]
    for i in range(10):
        Ptbl[(Rtbl[i][q0]+p0)%13][0]+=1
    for j in range(1,nq):
        qj=q[j]
        for n in range(10):
            for i in range(13):
                if Ptbl[i][j-1]>0:
                    ii=(i+Rtbl[n][qj])%13
                    Ptbl[ii][j]=(Ptbl[ii][j]+Ptbl[i][j-1])%MOD
    #printTbl(Ptbl)
    return Ptbl[5][nq-1]

if __name__=='__main__':
    s=readinput()
    ans=main(s)
    print(ans)

Submission status: Runtime Error

Solution code:
S = input()
N = len(S)
dp = []
for _ in range(N+1):
    dp.append([0] * 13)

for i in range(1, N+1):
    X = S[N-i]
    if X == '?':
        if i == 1:
            for j in range(10):
                dp[1][j] += 1
            continue
        for j in range(10):
            X = (j * pow(10, i-1, mod=13)) % 13
            for k in range(13):  # 上段の各あまりに対して、xのあまりを加える
                Y = dp[i-1][k]
                Z = (X + k) % 13  # 新たなあまり
                dp[i][Z] += Y

    else:
        X = int(X)
        X = (X * pow(10, i-1, mod=13)) % 13
        if i == 1:
            dp[1][X] += 1
            continue
        for k in range(13):  # 上段の各あまりに対して、xのあまりを加える
            Y = dp[i-1][k]
            Z = (X + k) % 13  # 新たなあまり
            dp[i][Z] += Y

print(dp[-1][5] % 1000000007)

Submission status: Runtime Error

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

tmp = copy.copy(S)
i = 0
while tmp[i] == '?':
  tmp[i] = ''
  i += 1
for i in range(len(tmp)):
  if tmp[i] == '?':
    tmp[i] = '0'
start = int(''.join(tmp))
  
# 探索範囲の最小値
#start = 10**(N-1)
if start % 13 < 5:
  r = start % 13
  start += (5-r)
elif start % 13 > 5:
  r = start % 13
  start += (13-r+5)

# 探索範囲の最大値 
end = 10**N
if end % 13 != 5:
  r = end % 13
  end -= (8+r)

# '?'のindexを取得
idxs = []
for i in range(N):
  if S[i] != '?':
    idxs.append(i)
    
count = 0
for i in range(start, end+1, 13):
  number = list(str(i))
  diff = N - len(number)
  if diff != 0:
    for j in range(diff):
      number.insert(0, '0')	# 先頭に0を追加
  #print(number, S)
  flag = 1
  for j in range(len(idxs)):
    idx = idxs[j]
    if S[idx] != number[idx]:
      flag = 0
      break
  if flag == 1:
    count+=1
print(count)

Submission status: Runtime Error

Solution code:
S = str(input())
s = [i for i in S]
ans = 0
mn = 0
mx = len(S)
for i in range(mx):
  if S[i].isnumeric():
    mn = mx-i-1
    break
    
start = 0
for i in range(int(S[mx-mn-1])*10**mn, 10**mx):
  if i % 13 == 5:
    start = i
    break
    
ans = 0
for i in range(start, 10**mx, 13):
  flg = True
  for j in range(1, len(str(i))+1):
    if (s[-j].isnumeric()) and (s[-j]!=str(i)[-j]):
      flg = False
      break
  if flg:
    ans += 1
  if ans >= 10**9+7:
    ans -= 10**9+7
    
print(ans)

Submission status: Runtime Error

Solution code:
////////////////////////////////////
////////////////////////////////////
////                            ////
////                            ////
////     Please give me AC!     ////
////     Please give me AC!     ////
////                            ////
////                            ////
////////////////////////////////////
////////////////////////////////////
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MOD=13;
const long double Pi=acos(-1);
using  P=pair<ll,ll>;
ll gcd(ll a,ll b){//aとbの最大公約数を返す//計算量は0(log(max(a,b))
  if(a%b==0){return b;}
  else{return gcd(b,a%b);}
}
ll lcm(ll a,ll b){//aとbの最小公倍数を返す//計算量は0(log(max(a,b))
  return a*b/gcd(a,b);
}
int pow(int x,int y){//x^yを返す//計算量は0(log(y))
  ll tmp=x,res=1;
  while(y){
    if(y%2){res=res*tmp%MOD;}
    y>>=1;
    tmp=tmp*tmp%MOD;
  }
  return res%MOD;
}
ll nature(ll a){//絶対値を返す
  if(a>=0){return(a);}
  else{return(-1*a);}
}
ll prime(ll a){//素数なら1を返す//計算量は0(sqrt(a))
  if(a==2){return 1;}
  else if(a%2==0 || a==1){return 0;}
  for(ll i=3;i*i<=a;i+=2){if(a%i==0){return 0;}}
  return 1;
}
vector<int> Z;
void z_algorithm(string str){//計算量はO(str.size())
  Z.resize(str.size());
  Z.at(0)=str.size();
  int m=1,n=0;
  while(m<(int)str.size()){
    while(m+n<(int)str.size()&&str.at(n)==str.at(m+n)){n++;}
    Z.at(m)=n;
    if(n==0){
      m++;
      continue;
    }
    int k=1;
    while(k+Z.at(k)<n){
      Z.at(m+k)=Z.at(k);
      k++;
    }
    m+=k;
    n-=k;
  }
}
int main(){
  string S;
  cin>>S;
  int dp[100020][13],mod=1e9+7;
  int dpcopy[13];
  for(int i=1;i<=(int)S.size();i++){
    if(S.at(i-1)=='?'){
      for(int j=0;j<13;j++){
        if(i==1 && j<10){
          int w=(int)S.size()-1;
          int a=pow(10,w)*j%MOD;
          dp[1][a]=1;
        }
        else if(i>1){
          for(int k=0;k<13;k++){
            dpcopy[k]=dp[i-1][k];
          }
          for(int k=0;k<10;k++){
            int w=(int)S.size()-i;
            int a=pow(10,w)*k%MOD;
            dp[i][j]+=dpcopy[(j-a+13)%13];
            dp[i][j]%=mod;
          }
          for(int k=0;k<13;k++){
            dp[i-1][k]=dpcopy[k];
          }
        }
      }
    }
    else{
      if(i==1){
        int w=(int)S.size()-i;
        int a=pow(10,w);
        dp[1][a]=1;
      }
      else{
        for(int j=0;j<13;j++){
          dpcopy[j]=dp[i-1][j];
        }
        int a=pow(10,(int)S.size()-i)*(S.at(i-1)-'0');
        a%=MOD;
        for(int j=0;j<13;j++){
          dp[i][j]=dpcopy[(j-a+13)%13];
        }
        for(int j=0;j<13;j++){
          dp[i-1][j]=dpcopy[j];
        }
      }
    }
  }
  cout<<dp[(int)S.size()][5]%mod<<endl;
}

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
// #include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <math.h>

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=(a);i<(b);i++)
#define sort(a) sort(a.begin(),a.end())
#define reverse(a) reverse(a.begin(),a.end())

template<class T> inline void chmin(T& a, T b) {if (a > b) a = b;}
template<class T> inline void chmax(T& a, T b) {if (a < b) a = b;}
const ll inf = 1LL<<60;



int main(){
  ios_base::sync_with_stdio(false); 
  cin.tie(NULL);
  string s;cin>>s;
  ll mod = pow(10,9)+7;
  vector<vector<ll>> dp(s.size()+1,vector<ll>(13,0));
  dp[0][0]=1;
  for(int i=0;i<s.size();i++){
    for(int j=0;j<13;j++){
      if(s[i]=='?'){
        for(int k=0;k<10;k++){
          dp[i+1][(j*10+k)%13]=(dp[i+1][(j*10+k)%13]+dp[i][j])%mod;
        }
      }else{
        int k=s[i]-'0';
        dp[i+1][(j*10+k)%13]=(dp[i+1][(j*10+k)%13]+dp[i][j])%mod;
      }
    }
  }
  cout<<dp[s.size()][5]%mod<<endl;

}

Submission status: Runtime Error

Solution code:
import numpy as np
from sys import stdin
s = stdin.readline()[:-1]

length = len(s)

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

s = list(reversed(s))

dp[0][0]=1
ten = 1
mod = 1000000007


for i in range(length):
	if s[i] == '?':
		for num in range(10):
			d = num*ten
			for j in range(13):
				k = (j+d)%13
				dp[i+1][k] += dp[i][j]
				dp[i+1][k] %= mod
	else:
		num = int(s[i])
		d = num*ten
		for j in range(13):
			k = (j+d)%13
			dp[i+1][k] += dp[i][j]
			dp[i+1][k] %= mod
	ten *= 10
	ten %= 13

print(int(dp[length][5]%mod))

Submission status: Runtime Error

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

s = input()
mod = 10**9+7
dp = [[0]*13 for _ in range(len(s))]
t = [1]
for i in range(len(s)-1):
    t.append(t[-1]*10%13)
t.reverse()
#print(t)
if (s[0]=="?"):
    for i in range(10):
        dp[0][t[0]*i%13] = +1
else:
    dp[0][t[0]*int(s[0])%13] += 1
for i in range(1,len(s)):
    if (s[i]=="?"):
        for j in range(13):
            for k in range(10):
                dp[i][(j + t[i]*k)%13] += dp[i-1][j]
                dp[i][(j + t[i]*k)%13] %= mod
    else:
        for j in range(13):
            #print(i,j,(j + t[i]*int(s[i]))%13)
            dp[i][(j + t[i]*int(s[i]))%13] += dp[i-1][j]
            dp[i][(j + t[i]*int(s[i]))%13] %= mod             
#print(dp)
print(dp[len(s)-1][5])import sys
input = sys.stdin.readline

s = input()
mod = 10**9+7
dp = [[0]*13 for _ in range(len(s))]
t = [1]
for i in range(len(s)-1):
    t.append(t[-1]*10%13)
t.reverse()
#print(t)
if (s[0]=="?"):
    for i in range(10):
        dp[0][t[0]*i%13] = +1
else:
    dp[0][t[0]*int(s[0])%13] += 1
for i in range(1,len(s)):
    if (s[i]=="?"):
        for j in range(13):
            for k in range(10):
                dp[i][(j + t[i]*k)%13] += dp[i-1][j]
                dp[i][(j + t[i]*k)%13] %= mod
    else:
        for j in range(13):
            #print(i,j,(j + t[i]*int(s[i]))%13)
            dp[i][(j + t[i]*int(s[i]))%13] += dp[i-1][j]
            dp[i][(j + t[i]*int(s[i]))%13] %= mod             
#print(dp)
print(dp[len(s)-1][5])

Submission status: Runtime Error

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

s = input()
mod = 10**9+7
dp = [[0]*13 for _ in range(len(s))]
t = [1]
for i in range(len(s)-1):
    t.append(t[-1]*10%13)
t.reverse()
#print(t)
if (s[0]=="?"):
    for i in range(10):
        dp[0][t[0]*i%13] = +1
else:
    dp[0][t[0]*int(s[0])%13] += 1
for i in range(1,len(s)):
    if (s[i]=="?"):
        for j in range(13):
            for k in range(10):
                dp[i][(j + t[i]*k)%13] += dp[i-1][j]
                dp[i][(j + t[i]*k)%13] %= mod
    else:
        for j in range(13):
            #print(i,j,(j + t[i]*int(s[i]))%13)
            dp[i][(j + t[i]*int(s[i]))%13] += dp[i-1][j]
            dp[i][(j + t[i]*int(s[i]))%13] %= mod             
#print(dp)
print(dp[len(s)-1][5])

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
# import time
# import itertools
# import pprint
# import copy # deepcopy用
# import collections
# import bisect
# import heapq
# from collections import deque
# from collections import Counter
# from fractions import gcd # >=Python3.5 # lcm（最小公倍数） = (a*b)//gcd(a,b)
# from fractions import Fraction
# from math import gcd # <Python3.5
# from math import sqrt

input = sys.stdin.readline
def main():

#---------------------------------------------------------

    # path = 'input.txt'
    # f = open(path, "r")
    
    # s = list(f.readline())
    s = list(input())
    # s.pop()
    s.reverse()
    
    MOD = 10**9+7
    dp  = np.array([0]*13)
    ndp = np.array([0]*13)
    tmp = np.arange(10)
    
    mul   = 1
    dp[0] = 1

    # t1 = time.time()

    for i in s:
        if i=='?':
            sh = tmp*mul%13
            for j in sh:
                ndp += np.append(dp[-j:],dp[:-j])
            ndp %= MOD
        else:
            sh = mul*int(i)%13
            ndp += np.append(dp[-sh:],dp[:-sh])
            ndp %= MOD

        dp  = ndp
        ndp = np.array([0]*13)
        mul *= 10

    # t2 = time.time()
    # print(t2-t1)

    print(dp[5])

#---------------------------------------------------------

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#

import sys
input=sys.stdin.readline

def main():
    MOD=10**9+7
    S=input().strip("\n")
    q=[]
    g=0
    S=S[::-1]
    m13=(1,10,9,12,3,4)
    for i in range(len(S)):
        if S[i] == "?":
            q.append(m13[i%6])
        else:
            x=int(S[i])
            g+=x*m13[i%6]
            g%=13
    N=len(q)
    q=[0]+q
    dp=[[0]*13 for i in range(N+1)]
    for j in range(10):
        dp[1][(j*q[1])%13]=1
    for i in range(2,N+1):
        for j in range(13):
            for k in range(10):
                x=(j-k*q[i])%13
                dp[i][j]+=dp[i-1][x]
                dp[i][j]%=MOD
    print(dp[N][(5-g)%13])
    
if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000000)

s = input()
n = len(s)

mod=10**9+7

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

ans=0
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 or c== j):
            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]%mod%mod)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000000)

s = input()
n = len(s)

mod=10**9+7

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

ans=0
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 or c== j):
            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: Runtime Error

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

def main():
    S = input()
    length = len(S)
    MOD = 10**9+7

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

    for i in range(1, length+1):
        if S[i-1] == '?':
            for j in range(10):
                for k in range(13):
                    dp[i][(10*k+j)%13] += dp[i-1][k]
                    dp[i][(10*k+j)%13] %= MOD

        else:
            x = int(S[i-1])

            for j in range(13):
                dp[i][(10*j+x)%13] += dp[i-1][j]
                dp[i][(10*j+x)%13] %= MOD
                
    print(dp[length][5])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
rom sys import stdin, setrecursionlimit


def main():
    mod = 10 ** 9 + 7
    input = stdin.buffer.readline
    s = list(input()[:-1].decode())
    s.reverse()
    n = len(s)

    p10 = [0] * n
    p10[0] = 1
    for i in range(1, n):
        p10[i] = 10 * p10[i - 1]

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

    for i in range(1, n):
        tmp_dp = [0] * 13
        if s[i] == '?':
            for j in range(13):
                for k in range(10):
                    tmp_dp[(k * p10[i] + j) % 13] += dp[j] % mod
        else:
            for j in range(13):
                tmp_dp[(int(s[i]) * p10[i] + j) % 13] += dp[j] % mod
        dp = tmp_dp

    print(dp[5] % mod)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Runtime Error

Solution code:
def main():
  s=list(input())
  n=len(s)
  dp=[0]*13
  mod=pow(10,9)+7
  if s[-1]=='?':
    dp=[1]*10+[0]*3
  else:
    dp[int(s[-1])]=1
  p_dp=[0]*13
  for i in range(2,n+1):
    if s[-i]=='?':
      for j in range(10):
        a=(j*pow(10,i-1,13))%13
        for k in range(13):
          p_dp[(a+k)%13]+=dp[k]
    else:
      j=int(s[-i])
      a=(j*pow(10,i-1,13))%13
      for k in range(13):
        p_dp[(a+k)%13]+=dp[k]
    
    for k in range(13):
      p_dp[k]%=mod
    dp=p_dp.copy()
    p_dp=[0]*13
  print(dp[5])

if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
s = input()
len_s = len(s)
mod = 10 ** 9 + 7
dp = [[0] * 13 for i in range(len_s)]

for i in range(len_s):
    if s[-(i + 1)] == '?':
        for j in range(13):
            if i == 0:
                if j < 10:
                    dp[i][j] = 1
                continue

            if dp[i - 1][j] > 0:
                for k in range(10):
                #k:先頭に加える数字
                    add = k * pow(10, i)
                    dp[i][(j + add)%13] = (dp[i][(j + add)%13] + dp[i - 1][j])%mod

    else:
        if i == 0:
            dp[i][int(s[-(i + 1)])] = 1
            continue

        add = int(s[-(i + 1)]) * pow(10, i)
        for j in range(13):
            if dp[i - 1][j] > 0:
                dp[i][(j + add)%13] = (dp[i][(j + add)%13] + dp[i - 1][j])%mod

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

Submission status: Runtime Error

Solution code:
S = list(input())
N = len(S)
dp = [ [0 for i in range(13)] for i in range(N+1)]
keta = 0.1
mod = 10**9 + 7

S.reverse()

for i in range(1,N+1):
  
  amaarr = [0 for ii in range(13)]
  c = S[i-1]
  keta *= 10 % mod
  if c == "?":
    for j in range(10):
      amari = int( keta * j % 13 )
      amaarr[amari] += 1
  else:
    amari = int( keta * int(c) % 13 )
    amaarr[amari] += 1
    
  if i == 1:
    for k in range(13):
      am = amaarr[k]
      dp[i][k] += am
      
  else:
    for k in range(13):
      am = amaarr[k]
      for l in range(13):
        dp[i][(l+k)%13] += dp[i-1][l] * am  % mod

         
print(dp[-1][5])

Submission status: Runtime Error

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

for i in range(1,N+1):
  
  amaarr = [0 for ii in range(13)]
  c = S[i-1]
  keta /= 10  
  if c == "?":
    for j in range(10):
      amari = int( keta * j % 13 )
      amaarr[amari] += 1
  else:
    amari = int( keta * int(c) % 13 )
    amaarr[amari] += 1
    
  if i == 1:
    for k in range(13):
      am = amaarr[k]
      dp[i][k] += am
      
  else:
    for k in range(13):
      am = amaarr[k]
      for l in range(13):
        dp[i][(l+k)%13] += dp[i-1][l] * am  % mod
         
print(dp[-1][5])

Submission status: Runtime Error

Solution code:
M = (10**9+7)
s = list(input())[::-1]

mo = []
fixed = 0
for i in range(len(s)):
  if s[i]!='?':
    t = int(s[i])
    fixed += (t*pow(10,i,13))%13
  else:
    t = []
    for j in range(10):
      t.append((j*pow(10,i,13)%13))
    mo.append(tuple(t))
    
dp = [[-1]*13 for _ in range(len(mo))]

for m in mo[0]:
  dp[0][m] = 1
for i in range(len(mo)-1):
  for j in range(13):
    if dp[i][j]==-1:
      continue
    for m in mo[i+1]:
      p = (j+m)%13
      if dp[i+1][p] == -1:
        dp[i+1][p] = dp[i][j] % M
      else:
        dp[i+1][p] += dp[i][j] 

ans = dp[-1][(18-fixed)%13] % M 
if dp[-1][(18-fixed)%13] == -1:
  print(0)
  exit()
print(ans)

Submission status: Runtime Error

Solution code:
M = (10**9+7)
s = list(input())[::-1]

mo = []
fixed = 0
for i in range(len(s)):
  if s[i]!='?':
    t = int(s[i])
    fixed += (t*pow(10,i,13))%13
  else:
    t = []
    for j in range(10):
      t.append((j*pow(10,i,13)%13))
    mo.append(tuple(t))
    
dp = [[-1]*13 for _ in range(len(mo))]

for m in mo[0]:
  dp[0][m] = 1
for i in range(len(mo)-1):
  for j in range(13):
    if dp[i][j]==-1:
      continue
    for m in mo[i+1]:
      p = (j-m)%13
      if dp[i+1][p] == -1:
        dp[i+1][p] = dp[i][j] % M
      else:
        dp[i+1][p] += dp[i][j] 
ans = dp[-1][(18-fixed)%13] % M 
print(ans)

Submission status: Runtime Error

Solution code:

#初期入力
import sys
input = sys.stdin.readline
import heapq
N = int(input())
connection   ={i:set() for i in range(1,N+1)}
A            =[i for i in range(N-1)]
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connection[a].add(b) # つながりを逆向きも含めて入力
    connection[b].add(a) # 
    A[i] =a,b            #色を出力するため

#色の数(各頂点の最大値)
color_max =0
root =0
for i,v in connection.items():
    if color_max < len(v) :
        color_max =len(v)
        root =i         #枝が一番多い所を根 ⇒スタート

#各頂点に色を準備⇒辺の色決定
aa=[]
color =0                                 #辺に塗る色の候補
node ={i:[] for i in range(1,N+1)} #頂点に使った色の管理
edge ={}
for a,b in A:
    edge[(a,b)] =-1                   #辺の色 -1で初期化
now_set =set() #=start
now_set.add(root) #=start
next =set()
next_next =set()
passed ={i:False for i in range(1,N+1)}
count =0
while -1 in edge.values(): #全て辺の色が-1以外＝塗り終わった
    for now in now_set: #幅優先探索
        next =connection[now]
        for nex_2 in next:
            count =0
            if node[now] !=[]:
                color =node[now][-1] +1
            while count < color_max:
                q,color =divmod(color,color_max)
                if color not in node[now] and color not in node[nex_2]:
                    n1,n2=0,0
                    if now > nex_2:
                        n1,n2 =nex_2,now
                    else:
                        n1,n2 =now,nex_2
                    edge[(n1,n2)] =color +1  #辺の色決定
                    node[now]   .append(color)
                    node[nex_2] .append(color)
                    passed[now] =True
                    #colored     =connection[nex_2] - passed
                    if passed[nex_2] ==False:
                        next_next.add(nex_2)  #つながっている頂点（次に探索する）
                    passed[nex_2] =nex_2
                    color   +=1
                    count   +=1
                    break
                else:
                    color +=1
                    count +=1
    now_set     .clear()
    now_set     |=next_next
    next_next   .clear()
    
#出力
print(color_max)
for i in A:
    print(edge[i])

Submission status: Runtime Error

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353

dp = [0] * (S + 1)

ans = 0
for a in A:
    dp[0] += 1
    for s in range(S + 1)[::-1]:
        if s + a <= S:
            dp[s + a] = (dp[s + a] + dp[s]) % MOD
    ans += dp[S]
    ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
S=input()
n=len(S)
t=[]
for i in range(13):
  t.append(0)
s=t.copy()

t[0]=1
jkmap=[]
for j in range(10):
  jkmap.append([])
  for k in range(13):
    jkmap[j].append((10*k+j)%13)
for i in range(n):
  if S[i]=='?':
    if i%2==0:
      for j in range(10):
        for k in range(13):
          s[jkmap[j][k]]=(t[jkmap[j][k]]+t[k])%(10**9+7)
    
  else:
    j=int(S[i])
    for k in range(13):
      t[jkmap[j][k]]=(s[jkmap[j][k]]+t[k])%(10**9+7)
print(t[5])

Submission status: Runtime Error

Solution code:
S=input()
n=len(S)
t=[]
for i in range(13):
  t.append(0)
s=t.copy()
t[0]=1
jkmap=[]
for j in range(10):
  jkmap.append([])
  for k in range(13):
    jkmap[j].append((10*k+j)%13)
for i in range(n):
  if S[i]=='?':
    tcopy=s.copy()
    for j in range(10):
      for k in range(13):
        tcopy[jkmap[j][k]]=(tcopy[jkmap[j][k]]+t[k])%(10**9+7)
    t=tcopy.copy()
  else:
    j=int(S[i])
    tcopy=s.copy()
    for k in range(13):
      tcopy[jkmap[j][k]]=(tcopy[jkmap[j][k]]+t[k])%(10**9+7)
    t=tcopy.copy()
print(t[5])

Submission status: Runtime Error

Solution code:
def main():
    S = input()[::-1]
    N = len(S)
    mod = 10 ** 9 + 7

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

    digit = 1
    for i, s in enumerate(S):
        if s == "?":
            num = tuple(range(10))
        else:
            num = (int(s), )

        ni = i + 1
        for j in range(13):
            for k in num:
                nj = (j + k * digit) % 13
                dp[ni][nj] += dp[i][j]
                dp[ni][nj] %= mod

        digit *= 10
        digit %= 13

    return dp[N][5]


if __name__ == "__main__":
    print(main())pyp

Submission status: Runtime Error

Solution code:
s=input()
l=len(s)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1 #初期値の設定
for i in range(l):
if s[i]=='?': #?のときは各値(0～9)について更新する
  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) #最後まで更新を行ったときのあまりが5となる数の個数が答え

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def main():
    S = input()
    N = len(S)

    # S = [int(s) if s!="?" else -1 for s in S ]
    dp = [[0] * 13 for _ in range(N+1)]

    s = S[0]
    if s == "?":
        for j in range(10):
            dp[0][j] += 1
    else:
        dp[0][int(s)%13] += 1
    for i in range(1,N):
        s = S[i]
        if s == "?":
            X = range(10)
        else:
            X = [int(s)]

        for j in range(0,13):
            ten_j = j*10
            for x in X:
                k = (ten_j+x)%13
                dp[i][k] += dp[i-1][j]
                # print(i,j,k)

    # print(dp)
    print(dp[N-1][5] % (10**9+7))



if __name__ == "__main__":
  main()