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
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[-2][5] % (10**9+7))



if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
import sys


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    S = input()
    N = len(S)
    dp = [[0] * 13 for _ in range(N)]

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

    for i in range(1, N):
        if S[N - i - 1] != "?":
            for k in range(13):
                j = int(S[N - i - 1])
                idx = (k + j * (10 ** i)) % 13
                dp[i][idx] += dp[i - 1][k]
                dp[i][idx] %= MOD
        else:
            for j in range(10):
                for k in range(13):
                    idx = (k + j * (10 ** i)) % 13
                    dp[i][idx] += dp[i - 1][k]
                    dp[i][idx] %= MOD

    print(dp[-1][5])


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;

const double PI=acos(-1.0);
const ll MOD=1000000007;

string S; ll dp[100010][13];
int input()
{
    cin>>S;
}

int solve()
{
    int N=S.length();
    // for(int i=0;i<13;++i) dp[1][i]=0ll;
    // if(S[0]=='?'){
    //     for(int j=0;j<10;++j){
    //         dp[1][j]=1ll;
    //     }
    // } else {
    //     int j=S[1]-'0';
    //     dp[1][j]=1ll;
    // }
    dp[0][0]=1ll;

    for(int i=0;i<N;++i){
        if(S[i]=='?'){
            for(int j=0;j<13;++j){
                for(int k=0;k<10;++k){
                   dp[i+1][(j*10+k)%13]+=dp[i][j];
                   dp[i+1][(j*10+k)%13]%=MOD;
               }
           }
        } else {
            int k=S[i]-'0';
            for(int j=0;j<13;++j){
                dp[i+1][(j*10+k)%13]+=dp[i][j];
                dp[i+1][(j*10+k)%13]%=MOD;
            }
        }
    }
    cout<<dp[N][5]<<endl;
}

int main()
{
    cin.tie();
    ios::sync_with_stdio(false);
    input();
    solve();
    return 0;
}

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

typedef long long ll;
typedef pair<int, int> P;

const ll mod =  1000000007;  //出力は (ans % mod + mod) % mod  (負の剰余を正にする)
const int inf = 1e9;
const long long INF = 1LL << 60;   // INF = 1152921504606846976

ll dp[100010][13];

int main()
{
    string s; cin >> s;
    dp[0][0] = 1;
    int n = s.size();
    rep(i,n) rep(j,13){
        if(s[i] == '?'){
            rep(k,10){
                dp[i+1][(j*10+k)%13] += dp[i][j];
                dp[i+1][(j*10+k)%13] %= mod;
            }
        }else{
            int nd = s[i] - '0';
            dp[i+1][(j*10+nd)%13] += dp[i][j];
            dp[i+1][(j*10+nd)%13] %= mod;
        }
    }
    cout << dp[n][5] << endl;
}

Submission status: Runtime Error

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

s=input()
l=len(s)
mod = 10**9+7
dp=[[0]*13 for _ in range(l+1)]

dp[0][0]=1 #初期値設定
for i in range(l):
  if s[i]!="?":
    for k in range(13):
      dp[i+1][(k*10+int(s[i]))%13]+=dp[i][k]
  else:
    for j in range(10):
      for k in range(13):
        dp[i+1][(k*10+j)%13]+=dp[i][k]
        
print(dp[-1][5]%mod)

Submission status: Runtime Error

Solution code:
import numpy as np
MOD = 1000000007

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(13):
            for num in range(10):
                state = (10*j+num)%13
                dp[i+1][state] += dp[i][j]
                dp[i+1][state] %= MOD
    else:
        num = int(s)
        for j in range(13):
            state = (10*j+num)%13
            dp[i+1][state] += dp[i][j]
            dp[i+1][state] %= MOD

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

Submission status: Runtime Error

Solution code:
import numpy as np
MOD = 1000000007

S = input()

dp = np.zeros((len(S)+1, 13))

dp[0][0] = 1
for i, s in enumerate(S):
    if s == '?':
        for j in range(13):
            for num in range(10):
                state = (10*j+num)%13
                dp[i+1][state] += dp[i][j]
                dp[i+1][state] %= MOD
    else:
        num = int(s)
        for j in range(13):
            state = (10*j+num)%13
            dp[i+1][state] += dp[i][j]
            dp[i+1][state] %= MOD

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

Submission status: Runtime Error

Solution code:
def main():
	readline = sys.stdin.readline
	s = tuple(input())
	length = len(s)

	dp = [[0 for _ in range(13)]for _ in range(length+1)]
	MOD = 10**9+7
	if s[-1] == '?':
		for i in range(10):
			dp[1][i] = 1
	else:
		dp[1][int(s[-1])] = 1

	for i in range(1,length):
		if s[-i-1] != '?':
			num = (int(s[-i-1]) * (10**i)) % 13
			for j in range(13):
				dp[i+1][j] = dp[i][(13-num+j)%13]
				dp[i+1][j] %= MOD
		else:
			num = (10**i) % 13
			a = 0
			for j in range(10):
				for k in range(13):
					dp[i+1][k] += dp[i][(13-a+k)%13]
					dp[i+1][k] %= MOD
				a += num

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

if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
import sys

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

	s = list(input())

	dp = [[0 for _ in range(13)]for _ in range(len(s)+1)]
	MOD = 10**9+7
	if s[-1] == '?':
		for i in range(10):
			dp[1][i] = 1
	else:
		dp[1][int(s[-1])] = 1

	for i in range(1,len(s)):
		if s[-i-1] != '?':
			num = (int(s[-i-1]) * (10**i)) % 13
			for j in range(13):
				dp[i+1][j] = dp[i][(13-num+j)%13]
				dp[i+1][j] % MOD
		else:
			for j in range(10):
				num = j * (10**i) % 13
				for k in range(13):
					dp[i+1][k] += dp[i][(13-num+k)%13]
					dp[i+1][k] % MOD

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

if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

S=list(ns())
S.reverse()

modmap=[[0]*10 for i in range(10**5)]
for i in range(10):
    modmap[0][i]=i

for i in range(1,10**5):
    for j in range(10):
        modmap[i][j]=(modmap[i-1][j]*10)%13


q_list=[]
moda=0
for i in range(len(S)):
    if(S[i]=='?'):
        q_list.append(i)
    else:
        moda=(moda+modmap[i][int(S[i])])%13


modlist=[[0]*13 for i in range(len(q_list))]
mlist=[i for i in range(13)]

for i in range(10):
    modlist[0][modmap[q_list[0]][i]]=1

for i in range(1,len(q_list)):
    for j in range(10):
        tmpmod=modmap[q_list[i]][j]
        for k in range(13):
            modlist[i][(tmpmod+k)%13]+=(modlist[i-1][k]%(10**9+7))

print(modlist[len(q_list)-1][mlist[5-moda]]%(10**9+7))

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

S=list(ns())
S.reverse()

modmap=[[0]*10 for i in range(10**5)]
for i in range(10):
    modmap[0][i]=i

for i in range(1,10**5):
    for j in range(10):
        modmap[i][j]=(modmap[i-1][j]*10)%13


q_list=[]
moda=0
for i in range(len(S)):
    if(S[i]=='?'):
        q_list.append(i)
    else:
        moda=(moda+modmap[i][int(S[i])])%13


modlist=[[0]*13 for i in range(len(q_list))]
mlist=[i for i in range(13)]

for i in range(10):
    modlist[0][modmap[q_list[0]][i]]=1

for i in range(1,len(q_list)):
    for j in range(10):
        tmpmod=modmap[q_list[i]][j]
        for k in range(13):
            modlist[i][(tmpmod+k)%13]+=(modlist[i-1][k]%(10**9+7))

print(modlist[len(q_list)-1][mlist[5-moda]]%(10**9+7))

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

S=list(ns())
S.reverse()

modmap=[[0]*10 for i in range(10**5)]
for i in range(10):
    modmap[0][i]=i

for i in range(1,10**5):
    for j in range(10):
        modmap[i][j]=(modmap[i-1][j]*10)%13


q_list=[]
moda=0
for i in range(len(S)):
    if(S[i]=='?'):
        q_list.append(i)
    else:
        moda=(moda+modmap[i][int(S[i])])%13


modlist=[[0]*13 for i in range(len(q_list))]
mlist=[i for i in range(13)]

for i in range(10):
    modlist[0][modmap[q_list[0]][i]]=1

for i in range(1,len(q_list)):
    for j in range(10):
        tmpmod=modmap[q_list[i]][j]
        for k in range(13):
            modlist[i][(tmpmod+k)%13]+=(modlist[i-1][k]%(10**9+7))

print(modlist[len(q_list)-1][mlist[5-moda]])

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

S=list(ns())
S.reverse()

modmap=[[0]*10 for i in range(10**5)]
for i in range(10):
    modmap[0][i]=i

for i in range(1,10**5):
    for j in range(10):
        modmap[i][j]=(modmap[i-1][j]*10)%13


q_list=[]
moda=0
for i in range(len(S)):
    if(S[i]=='?'):
        q_list.append(i)
    else:
        moda=(moda+modmap[i][int(S[i])])%13


modlist=[[0]*13 for i in range(len(q_list))]
mlist=[i for i in range(13)]

for i in range(10):
    modlist[0][modmap[q_list[0]][i]]=1

for i in range(1,len(q_list)):
    for j in range(10):
        tmpmod=modmap[q_list[i]][j]
        for k in range(13):
            modlist[i][(tmpmod+k)%13]+=modlist[i-1][k]

print(modlist[len(q_list)-1][mlist[5-moda]]%(10**9+7))

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

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

a=1
for i in range(1,len_s):
    a=10*a%13
    if s[-(i+1)]!='?':
        temp_S=int(s[-(i+1)])
        amari=(temp_S*a)%13
        for j in range(13):
            dp[i][(amari+j)%13]+=dp[i-1][j]%mod

    else:
        for k in range(10):
            amari=(k*a)%13
            for l in range(13):
                dp[i][(amari+l)%13]+=dp[i-1][l]%mod
#print(*dp,sep='\n')
print(dp[-1][5]%mod)

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

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

for i in range(1,len_s):

    if s[-(i+1)]!='?':
        temp_S=int(s[-(i+1)])
        amari=(temp_S*10**i)%13
        for j in range(13):
            dp[i][(amari+j)%13]=(dp[i][(amari+j)%13]+dp[i-1][j])%mod

    else:
        for k in range(10):
            amari=(k*10**i)%13
            for l in range(13):
                dp[i][(amari+l)%13]=(dp[i][(amari+l)%13]+dp[i-1][l])%mod
#print(*dp,sep='\n')
print(dp[-1][5]%mod)

Submission status: Runtime Error

Solution code:
#import numpy as np
import sys
import numpy
input=sys.stdin.buffer.readline
s=input()
n=len(s)
mod=10**9+7
dp=np.array([[0 for _ in range(13)] for _ in range(n)])
for i,x in enumerate(s):
    if i==0:
        if x=='?':
            for j in range(10):
                dp[0][j]=1
        else:
            num=ord(x)-ord('0')
            dp[0][num]=1
    else:
        if x=='?':
            for j in range(10):
                for jj in range(13):
                    if dp[i-1][jj]>0:
                        dp[i][(10*jj+j)%13]=(dp[i][(10*jj+j)%13]+dp[i-1][jj])
        else:
            num=ord(x)-ord('0')
            for j in range(13):
                if dp[i-1][j]>0:
                    dp[i][(10*j+num)%13]=(dp[i][(10*j+num)%13]+dp[i-1][j])
print(dp[-1][5]%mod)

Submission status: Runtime Error

Solution code:
S = input()
L = len(S)

MOD = 10 ** 9 + 7
dp = [[0] * 13 for _ in range(15)]
dp[0][0] = 1
for i in range(L):
    j = -1 if S[i] == "?" else int(S[i])
    if j > -1:
        # jが確定しているので、jを全探索する必要はなく、前回桁までの組み合わせの数にjを足して次のDPへ入れる
        # jが確定しているから数字の組み合わせ自体が増えるわけではない
        # そのためこれまで確定していた桁に対して、jを追加した場合のあまりを単純に移送することになる
        
        # 前回桁までの数 * 10 + j をすると、今回桁をjにしたときのあまりがわかる
        # 3?1 → 301 % 13 = 2, 30 % 13 = 4であるから、ki=4のとき、dp[i][4]の数値をdp[i+1][2]に足す
        # 30と4はmod13の世界では合同になっている
        # すなわち*10した結果である300と40も合同
        # そこにjを足した数 300+jと40+jもまた合同であると言える、ともにあまりは2
        # ここでは具体的な値である30は計算していないが、その具体的な数と合同である数字を用いて、今回桁で作成可能な数字のmodを数えているdp[i+1][2]にdp[i][4]を突っ込むことになる
        # modの世界では両辺に同じ数をかけても合同であるという性質を用いて、10をかけながら、桁ごとに数値を足していっていることになる

        for ki in range(13):
            dp[i+1][(ki * 10 + j) % 13] += dp[i][ki]
    else:
        # jが確定していないので、jになりうる値を全て試す
        # 0-9の10パターンの数字が考えられるので、全ての組み合わせ自体は*10になる
        # ? だと10パターン ??だと100パターンになるので、?が来ると、数字の組み合わせが10倍になるのは自明
        # 10**(?の数) の組み合わせの総数になる
        for j in range(10):
            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[L][5])

Submission status: Runtime Error

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

S=input()
n=len(S)
R=[0]*13
cnt=[0]*13
Pow=[[] for i in range(6)]
mod=10**9+7

for i in range(6):
    c=10**i
    for j in range(10):
        Pow[i].append(c*j%13)
ans=0
flag=0
for i in range(n):
    if S[n-i-1]=="?":
        P=Pow[i%6]
        if flag==0:
            for p in P:
                R[p]=1
                flag=1
        else:
            for j in range(10):
                for k in range(13):
                    cnt[(k+P[j])%13]+=R[k]%mod
            R=cnt
            cnt=[0]*13
    else:
        x=int(S[n-i-1])
        ans+=Pow[i%6][x]
ans%=13
print(R[(18-ans)%13]%mod)

Submission status: Runtime Error

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

S=input()
n=len(S)
R=[0]*13 #剰余テーブル
cnt=[0]*13
Pow=[[] for i in range(6)] #10の累乗の剰余テーブル
mod=10**9+7

for i in range(6):
    c=10**i
    for j in range(10):
        Pow[i].append(c*j%13)
print(Pow)
ans=0
flag=0
for i in range(n):
    if S[n-i-1]=="?":
        P=Pow[i%6] #当該の剰余テーブル
        if flag==0:
            for p in P:
                R[p]=1
                flag=1
        else:
            for j in range(10):
                for k in range(13):
                    cnt[(k+P[j])%13]+=R[k]%mod
            R=cnt
            cnt=[0]*13
    else:
        x=int(S[n-i-1])
        ans+=Pow[i%6][x]
        print(x,ans)
    print(R,i)
    print(sum(R))
ans%=13
print(R[(18-ans)%13]%mod)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

S = input()
S = S[::-1]
LS = len(S)

MOD = 10 ** 9 + 7


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

for i in range(LS):
    if S[i] != '?':
        d = int(S[i])
        md = (d * pow(10, i, 13)) % 13

        if md == 0:
            dp[i + 1] = dp[i]
        else:
            dp[i + 1][md:] = dp[i][:-md]
            dp[i + 1][:md] = dp[i][-md:]
    else:
        t = pow(10, i, 13)
        for k in range(10):
            md = (k * t) % 13

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

print(dp[LS][5])

Submission status: Runtime Error

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
S = sr()
# 桁DP, 上から
dp = [0] * 13
dp[0] = 1
for i in range(len(S)):
    prev = dp.copy()
    num = S[i]
    dp = [0] * 13
    if num != '?':
        num = int(num)
        for j in range(13):
            dp[(10*j+num)%13] = prev[j]
    else:
        for j in range(13):
            for k in range(10):
                dp[(10*j+k)%13] += prev[j]
            dp[j] %= MOD

answer = dp[5]
print(answer%MOD)

Submission status: Runtime Error

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
mod=10**9+7
a,b,n=map(int,input().split())
def primes(x):
  is_prime=[True]*(x+1)
  is_prime[0]=False
  is_prime[1]=False
  for i in range(2,int(x**0.5)+1):
    if not is_prime[i]:
      continue
    for j in range(i*2,x+1,i):
      is_prime[j]=False
  return [i for i in range(x+1) if is_prime[i]]
P=primes(b)
ans=1
for p in P:
  ord=1
  ord_p=0
  while True:
    ct=b//(p**ord)-(a-1)//(p**ord)
    if ct:
      ord_p+=pow(ct,n,mod-1)
      ord+=1
    else:
      break
  ord_p%=mod-1
  ans=(ans*(pow(p,ord_p,mod)))%mod
print(ans)

Submission status: Runtime Error

Solution code:
S = input()
dp = [[0] * 13 for _ in range(10**5)]
MOD = 10 ** 9 + 7
dp[0][0] = 1
n = len(S)
for i in range(n):
    if S[i] == "?":
        c = -1
    else:
        c = ord(S[i]) - ord('0')

    for j in range(10):
        if c != -1 and c != j:
            continue
        for ki in range(13):
            dp[i + 1][(ki * 10 + j) % 13] += dp[i][ki]

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

print(dp[n][5])

Submission status: Runtime Error

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

DP = [[0 for _ in range(13)] for _ in range(n)]

if s[-1] == '?':
    for i in range(0,10):
        DP[0][i] += 1
else:
    DP[0][int(s[-1])] = 1

# 下2桁目から順に見ていく
for i in range(1,n):
    num_s = s[n-(i+1)]
    baisu = 10 ** i
    if num_s != '?':
        now = int(num) * baisu
        res = now % 13
        # 元の余りj -> (res+j)%13 が今回の余り 
        for j in range(13):
            DP[i][(j+res)%13] += DP[i-1][j]
            DP[i][(j+res)%13] %= mod
    else:
        for k in range(10):
            now = k * baisu
            res = now % 13
            # 元の余りj -> (res+j)%13 が今回の余り
            for j in range(13):
                DP[i][(j+res)%13] += DP[i-1][j]
                DP[i][(j+res)%13] %= mod

ans = DP[n-1][5]
print(ans)

Submission status: Runtime Error

Solution code:
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
s=list(input())
mod=10**9+7
U=[[0 for i in range(10) ]for k in range(13)]
for i in range(13):
    for j in range(10):
        U[i][j]=((i-j)*K)%13
K=modinv(10,13)
dp=[[0 for k in range(13)] for i in range(len(s))]
#dp[i][j]=初めのindex=i番目まで見たときに、あまりがjになるような方法の総数
num=s[0]
if s[0]=="?":
    for i in range(10):
        dp[0][i]=1
else:
    number=int(s[0])
    dp[0][number]=1

for i in range(1,len(s)):
    if s[i]=="?":
        for k in range(13):
            for j in range(10):
                dp[i][k]+=dp[i-1][U[k][j]]
        dp[i][k]=dp[i][k]%mod
    else:
        number=int(s[i])
        for k in range(13):
            dp[i][k]=dp[i-1][U[k][number]]%mod
print(dp[len(s)-1][5]%mod)

Submission status: Runtime Error

Solution code:
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
S=input()
s=[0 for i in range(len(s))]
for i in range(len(s)):
    if S[i]=="?":
        s[i]=10
    else:
        s[i]=int(S[i])

mod=10**9+7
K=modinv(10,13)
dp=[[0 for k in range(13)] for i in range(len(s))]
#dp[i][j]=初めのindex=i番目まで見たときに、あまりがjになるような方法の総数
num=s[0]
if s[0]==10:
    for i in range(10):
        dp[0][i]=1
else:
    number=s[0]
    dp[0][number]=1

for i in range(1,len(s)):
    if s[i]==10:
        for k in range(13):
            for j in range(10):
                dp[i][k]+=dp[i-1][((k-j)*K)%13]
        dp[i][k]=dp[i][k]%mod
    else:
        number=s[i]
        for k in range(13):
            dp[i][k]=dp[i-1][((k-number)*K)%13]
print(dp[len(s)-1][5]%mod)

Submission status: Runtime Error

Solution code:
S=list(input())
for i in range(int(input())):
    q=input()
    if q=='1':
        S.reverse()
    else:
        a,f,c=q.split()
        S=[c]+S if f=='1' else S+[c] 
print(''.join(S))

Submission status: Runtime Error

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

dp = [[0] * 13 for _ in range(len(s)+1)]
for i in range(10):
    if s[0] == "?":
        dp[1][i] += 1
    else:
        dp[1][int(s[0])] = 1
        break

for i, v in enumerate(s):
    if i == 0:
        continue
    for j in range(13):
        if v != "?":
            dp[i + 1][(10 * j + int(v))] += dp[i][j]
            dp[i + 1][(10 * j + int(v))] %= mod
            continue
        for k in range(10):
            x = (10 * j + k) % 13
            dp[i + 1][x] %= mod

print(dp[-1][5])

Submission status: Runtime Error

Solution code:
import math
import copy
from copy import deepcopy
import sys
import fractions
import numpy as np
from functools import reduce
import statistics
import heapq

# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

def getInputStr():
    inputStr = str(input())
    return inputStr

data = getInputStr()

a = str(data)
listStr = []
listStr = list(a)

n = len(listStr)
# listStr.reverse()

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

# MOD = 10 ** 9 + 7
MOD = 1000000000 + 7

for i in range(n):
    if listStr[i] == "?":
        c = -1
    else:
        c = int(listStr[i])

    for j in range(10):
        if c != -1 and c != j:
            continue
        for ki in range(13):
            dp[i+1][(ki *10 + j) % 13] += dp[i][ki]

    for j in range(13):
        dp[i+1][j] %= MOD
res = dp[n][5]
print(res)


# for i in range(len(listStr)):
#     # keta = pow(10, i) % 13
#
#     if listStr[i] == "?":
#         for k in range(10):
#             for j in range(13):
#                 dp[i+1][int(((k*keta)%13 + j) % 13)] += dp[i][j]
#                 # dp[i+1][int(((k*keta)%13 + j) % 13)] += dp[i][j]
#     else:
#         k = int(listStr[i])
#         for j in range(13):
#             dp[i + 1][int(((k * keta) % 13 + j) % 13)] += dp[i][j]
#
# ans = dp[len(listStr)][5] % INF
# print(ans)

Submission status: Runtime Error

Solution code:
import math
import copy
from copy import deepcopy
import sys
import fractions
import numpy as np
from functools import reduce
import statistics
import heapq

# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

def getInputStr():
    inputStr = str(input())
    return inputStr

data = getInputStr()

a = str(data)
listStr = []
listStr = list(a)

n = len(listStr)
# listStr.reverse()

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

# MOD = 10 ** 9 + 7
MOD = pow(10, 9) + 7

for i in range(n):
    if listStr[i] == "?":
        c = -1
    else:
        c = int(listStr[i])

    for j in range(10):
        if c != -1 and c != j:
            continue
        for ki in range(13):
            dp[i+1][(ki *10 + j) % 13] += dp[i][ki]

    for j in range(13):
        dp[i+1][j] %= MOD
res = dp[n][5]
print(res)


# for i in range(len(listStr)):
#     # keta = pow(10, i) % 13
#
#     if listStr[i] == "?":
#         for k in range(10):
#             for j in range(13):
#                 dp[i+1][int(((k*keta)%13 + j) % 13)] += dp[i][j]
#                 # dp[i+1][int(((k*keta)%13 + j) % 13)] += dp[i][j]
#     else:
#         k = int(listStr[i])
#         for j in range(13):
#             dp[i + 1][int(((k * keta) % 13 + j) % 13)] += dp[i][j]
#
# ans = dp[len(listStr)][5] % INF
print(ans)

Submission status: Runtime Error

Solution code:
import math
import copy
from copy import deepcopy
import sys
import fractions
import numpy as np
from functools import reduce
import statistics
import heapq

# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

def getInputStr():
    inputStr = str(input())
    return inputStr

data = getInputStr()

a = str(data)
listStr = []
listStr = list(a)

n = len(listStr)
# listStr.reverse()

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

MOD = 10 ** 9 + 7

for i in range(n):
    if listStr[i] == "?":
        c = -1
    else:
        c = int(listStr[i])

    for j in range(10):
        if c != -1 and c != j:
            continue
        for ki in range(13):
            dp[i+1][(ki *10 + j) % 13] += dp[i][ki]

    for j in range(13):
        dp[i+1][j] %= MOD
res = dp[n][5]
print(res)


# for i in range(len(listStr)):
#     # keta = pow(10, i) % 13
#
#     if listStr[i] == "?":
#         for k in range(10):
#             for j in range(13):
#                 dp[i+1][int(((k*keta)%13 + j) % 13)] += dp[i][j]
#                 # dp[i+1][int(((k*keta)%13 + j) % 13)] += dp[i][j]
#     else:
#         k = int(listStr[i])
#         for j in range(13):
#             dp[i + 1][int(((k * keta) % 13 + j) % 13)] += dp[i][j]
#
# ans = dp[len(listStr)][5] % INF
print(ans)