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:
total_cnt = 0

def check(S):
	return True if (int(S) % 13) == 5 else False

def calc(S):
	for j in range(10):
		S1 = S.replace("?", str(j), 1)
		if "?" in S1:
			calc(S1)
			continue
		else:
			global total_cnt
			if check(S1):
				total_cnt += 1


def test(S):
	global total_cnt
	if "?" in S:
		calc(S)
	else:
		total_cnt += 1 if check(S) else 0

	MAX = 10**9 + 7
	print(str(total_cnt % MAX))


if __name__ == "__main__":
	S = input()
	test(S)

Submission status: Runtime Error

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

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

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

print(dp[len(s)-1][5])

Submission status: Runtime Error

Solution code:
import numpy as np

x = 1000000007

S = input()
S = [int(s) if s != '?' else s for s in S]
S = S[::-1]

r = np.zeros((13,))
new_r = np.zeros((13,))

r[0] = 1

for i, s in enumerate(S):
    for j in range(10):
        if s != '?' and s != j:
            continue

        digit_r = ((10 ** i) * j) % 13

        for k in range(13):
            new_r[(digit_r + k) % 13] += r[k]

    new_r %= x

    r = new_r
    new_r = np.zeros((13,))

print(int(r[5] % x))

Submission status: Runtime Error

Solution code:
import re
number=input()
number=number.replace("?",".",100000)
length=len(number)

replica=number
while True:
    if replica[0]==".":
        replica=replica[1:]
    else:
        break
replen=len(replica)

minnum=10*(replen-1)
i=minnum//13
sumnum=0
while True:
    checknum=str(13*i+5)
    if len(checknum)<replen:
        i+=1
        continue
    g=length-replen 
    if checknum[-1*replen]!=number[-1*replen]:
        i+=1
        continue
    while len(checknum)<length:
        checknum="0"+checknum

    if len(checknum)>length:
        break
        
    m=re.match(number,checknum)
    if m:
        sumnum+=1
        sumnum=sumnum%1000000007
    i+=1
    
print(sumnum)

Submission status: Runtime Error

Solution code:
s = input()
n = len(s)
MOD = 1e9 + 7
dp = [[0] * 13 for _ in range(n)]
for i in range(10):
	if s[0] == "?":
		dp[0][i] = 1
	else:
		cur = ord(s[0]) - ord("0")
		dp[0][cur] = 1
for i in range(1, n):
	if s[i] != "?":
		cur = ord(s[i]) - ord("0")
		for j in range(13):
			dp[i][(10 * j + cur) % 13] += dp[i - 1][j]
	else:
		for j in range(13):
			for cur in range(10):
				dp[i][(10 * j + cur) % 13] += dp[i - 1][j]
#print(dp)
print(int(dp[n - 1][5] % MOD))

Submission status: Runtime Error

Solution code:
import itertools
S = input()[::-1]
mod = 10**9 + 7
A = [0] * 13
N = 0
for i, v in enumerate(S):
    p = pow(10, i, 13)
    if v == '?':
        A[p] += 1
    else:
        N += int(v) * p
        N %= 13
dp = [0] * 13
dp[N] = 1
for i, v in enumerate(A):
    for _ in range(v):
        dp_old = dp.copy()
        for j, k in itertools.product(range(1, 10), range(13)):
            x = (j * i + k) % 13
            dp[x] += dp_old[k]
            dp[x] %= mod
print(dp[5])

Submission status: Runtime Error

Solution code:
import re
number=input()
number=number.replace("?",".",100000)
length=len(number)

replica=number
while True:
    if replica[0]==".":
        replica=replica[1:]
    else:
        break
replen=len(replica)

print()


i=0
sumnum=0
while True:
    checknum=str(13*i+5)
    if len(checknum)<replen:
        i+=1
        continue
    g=length-replen 
    if checknum[-1*replen]!=number[-1*replen]:
        i+=1
        continue
    while len(checknum)<length:
        checknum="0"+checknum

    if len(checknum)>length:
        break
        
    m=re.match(number,checknum)
    if m:
        sumnum+=1
        sumnum=sumnum%1000000007
        print(checknum)
    i+=1
    
print(sumnum)

Submission status: Runtime Error

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

MOD = 10 ** 9 + 7

N = len(S)
DP = np.zeros((N+1, 13), dtype=np.int32)
DP[0, 0] = 1

for _i, s in enumerate(S):
    i = _i + 1

    if s == '?':
        candidate = range(10)
    else:
        candidate = [int(s)]

    for j in range(13):
        for c in candidate:
            m = (j * 10 + c) % 13
            DP[i, m] += DP[i-1, j]
    DP[i] %= MOD

print(DP[-1, 5])

Submission status: Runtime Error

Solution code:
import re
number=input()
number=number.replace("?",".",100000)
length=len(number)

replica=number
while True:
    if replica[0]==".":
        replica=replica[1:]
    else:
        break
replen=len(replica)

i=0
sumnum=0
while True:
    checknum=str(13*i+5)
    if len(checknum)<replen:
        i+=1
        continue
    checklength=len(checknum)
    if checklength<length:
        while len(checknum)!=length:
            checknum="0"+checknum

    if len(checknum)==length:
        m=re.match(number,checknum)
        if m:
            sumnum+=1
            sumnum=sumnum%1000000007
    
            
    if len(checknum)>length:
        break
    i+=1
    
print(sumnum)

Submission status: Runtime Error

Solution code:
dp = [0 for _ in range(N)]
dp[0] = 1
for s in reversed(S):
  dp2 = [0 for _ in range(N)]
  if s == "?":
    for d in range(10):  # 0 ~ 9
      for n in range(N):
        index = (d * k + n) % N
        dp2[index] += dp[n]
        dp2[index] %= MOD 
  else:
    d = int(s)
    for n in range(N):
      index = (d * k + n) % N
      dp2[index] += dp[n]
      dp2[index] %= MOD 
  dp = dp2
  k *= 10 % N
print(dp[5])

Submission status: Runtime Error

Solution code:
package main

import (
	"fmt"
)

func main() {
	fmt.Println(1)
}

Submission status: Runtime Error

Solution code:
package main

import (
	"fmt"
	"math"
)

func main() {
	var S string
	fmt.Scan(&S)
	N, MOD := 13, int(math.Pow(10, 9))+7
	dp, k := make([]int, N), 1
 dp[0] = 1
	for i := len(S) - 1; i >= 0; i-- {
		dp2 := make([]int, N)
	 if S[i] == '?' {
			for d := 0; d <= 9; d++ {
				for n := 0; n < N; n++ {
					index := (k*d + n) % N
					dp2[index] += dp[n]
					dp2[index] %= MOD
				}
			}
		} else {
			d := int(S[i] - '0')
			for n := 0; n < N; n++ {
				index := (k*d + n) % N
				dp2[index] += dp[n]
				dp2[index] %= MOD
			}
		}
		dp = dp2
		k *= 10
		k %=  N
	}
	fmt.Println(dp[5])
}

Submission status: Runtime Error

Solution code:
s = input()
l = len(s)
ns = s.replace('?' ,'0')
c1 = [1 if i != '?' else 0 for i in s]
c2 = [i for i in range(l) if s[i] == '?'][::-1]
lc2 = len(c2)
cout = 0
for i in range(10 ** lc2):
    num = int(ns)
    si = str(i)
    lsi = len(si)
    for j in range(lsi):
        num += int(si[j]) * (10 ** c2[lc2-lsi:][j])
    if num % 13 == 5:
        cout += 1
print(cout)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define SZ(x) ((int)(x).size())
typedef long long ll;
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout.setf(ios::fixed); cout.precision(20);
    string s; cin >> s;
    int n = SZ(s);
    vector<vector<ll>> dp(n + 10, vector<ll>(15, 0ll));
    for (int i = 0; i < 10; i++) {
        dp[0][i] = (s[0] == '?' || (s[0] - '0') == i);
    }
    const ll mod = (ll) 1e9 + 7;
    for (int i = 1; i < n; i++) {
        if (s[i] == '?') {
            for (int j = 0; j < 13; j++) {
                for (int k = 0; k < 10; k++) {
                    dp[i][(10 * j + k) % 13] += dp[i - 1][j];
                    dp[i][(10 * j + k) % 13] %= mod;
                }
            }
        } else {
            for (int j = 0; j < 13; j++) {
                int k = s[i] - '0';
                dp[i][(10 * j + k) % 13] += dp[i - 1][j];
                dp[i][(10 * j + k) % 13] %= mod;
            }
        }
    }
    cout << dp[n - 1][5] << "\n";
}

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <math.h>
#include <vector>
using namespace std;
 
int main() {
  string S;
  cin >> S;
  int N = 13;
  vector<int> dp(N, 0);
  dp[0] = 1;
  int k = 1;
  int MOD = pow(10, 9) + 7;
  for (int i = S.size() - 1; i >= 0; i--) {
    vector<int> dp2(N, 0);
    if (S[i] == '?') {
      for (int d = 0; d <= 9; d++) {
        for (int n = 0; n < N; n++) {
          int index = (k * d + n) % N;
          dp2[index] += dp[n];
          dp2[index] %= MOD;
        }
      }
    } else {
      int d = S[i] - '0';
      for (int n = 0; n < N; n++) {
        int index = (k * d + n) % N;
        dp2[index] += dp[n];
        dp2[index] %= MOD;
      }
    }
    dp = dp2;
    // for(int i=0; i < dp2.size(); i++) cout << dp[i] << " "; cout << endl;
    k *= 10 % N;
  }
  cout << dp[5] << endl;
  return 0;
}

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <math.h>
#include <vector>
using namespace std;
 
int main() {
  string S;
  cin >> S;
  int N = 13;
  vector<int> dp(N, 0);
  dp[0] = 1;
  int k = 1;
  int MOD = pow(10, 9) + 7;
  for (int i = S.size() - 1; i >= 0; i--) {
    vector<int> dp2(N, 0);
    if (S[i] == '?') {
      for (int d = 0; d <= 9; d++) {
        for (int n = 0; n < N; n++) {
          int index = (k * d + n) % N;
          dp2[index] += dp[n];
          dp2[index] %= MOD;
        }
      }
    } else {
      int d = S[i] - '0';
      for (int n = 0; n < N; n++) {
        int index = (k * d + n) % N;
        dp2[index] += dp[n];
        dp2[index] %= MOD;
      }
    }
    dp = dp2;
    // for(int i=0; i < dp2.size(); i++) cout << dp[i] << " "; cout << endl;
    k *= 10 % N;
  }
  cout << dp[5] << endl;
}

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <math.h>
#include <vector>
using namespace std;

int main() {
  string S;
  cin >> S;
  int N = 13;
  vector<int> dp(N, 0);
  dp[0] = 1;
  int k = 1;
  int MOD = pow(10, 9) + 7;
  for (int i = S.size() - 1; i >= 0; i--) {
    vector<int> dp2(N, 0);
    if (S[i] == '?') {
      for (int d = 0; d <= 9; d++) {
        for (int n = 0; n < N; n++) {
          int index = (k * d + n) % N;
          dp2[index] += dp[n];
          dp2[index] %= MOD;
        }
      }
    } else {
        int d = S[i] - '0';
        for (int n = 0; n < N; n++) {
          int index = (k * d + n) % N;
          dp2[index] += dp[n];
          dp2[index] %= MOD;
        }
    }
    dp = dp2;
    k *= 10 % MOD;
  }
  cout << dp[5] << endl;
}

Submission status: Runtime Error

Solution code:
cnt=0
 
def calcuration(i,A,B):
        global cnt
        if(A[i]=="?"):
                for k in range(10):
                        tmp=""
                        B[i]=k
                        if(i!=len(A)-1):
                                calcuration(i+1,A,B)
                        else:
                                for para2 in B:
                                        tmp+=str(para2)
                                tmp = int(tmp)
                                #print(tmp)
                                if(tmp%13==5):
                                        #print("OK")
                                        cnt+=1
        else:
                if(i!=len(A)-1):
                        calcuration(i+1,A,B)
                else:
                        tmp=""
                        for para2 in B:
                                tmp+=str(para2)
                        tmp = int(tmp)
                        #print(tmp)
                        if(tmp%13==5):
                                #print("OK")
                                cnt+=1
 
 
A = list(input())
B = A[:]
 
for num,para in enumerate(B):
    if(para=="?"):
        B[num]=0
 
calcuration(0,A,B)
 
print(cnt%(10**9+7))

Submission status: Runtime Error

Solution code:
cnt=0

def calcuration(i,A,B):
        global cnt
        if(A[i]=="?"):
                for k in range(10):
                        tmp=""
                        B[i]=k
                        if(i!=len(A)-1):
                                calcuration(i+1,A,B)
                        else:
                                for para2 in B:
                                        tmp+=str(para2)
                                tmp = int(tmp)
                                print(tmp)
                                if(tmp%13==5):
                                        #print("OK")
                                        cnt+=1
        else:
                if(i!=len(A)-1):
                        calcuration(i+1,A,B)
                else:
                        tmp=""
                        for para2 in B:
                                tmp+=str(para2)
                        tmp = int(tmp)
                        #print(tmp)
                        if(tmp%13==5):
                                #print("OK")
                                cnt+=1


A = list(input())
B = A[:]

for num,para in enumerate(B):
    if(para=="?"):
        B[num]=0

calcuration(0,A,B)

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

Submission status: Runtime Error

Solution code:
s = [int(x) if x!='?' else -1 for x in input()]
??2??5

mod = 1000000007
length = len(s)
ans = list([0]*13 for i in range(length+1))
ans[0][0] = 1

mod_x10 = [0]*13
for i in range(13):
    mod_x10[i] = i * 10 % 13 - 14

for i in range(length):
    if s[i] == -1:
        for j in range(13):
            x = mod_x10[j]
            for k in range(10):
                x = x + 1
                ans[i+1][x] += ans[i][j] % mod
    else:
        for j in range(13):
            ans[i+1][(mod_x10[j] + s[i] + 1) % 13] += ans[i][j] % mod

print('a')
print(ans[length][5] % mod)

Submission status: Runtime Error

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

answer = 0
  
clear = []
unclear = []   
for i in range(N):
    if S[i] == "?":
        unclear.append(10 ** (N - i - 1))
        clear.append(0)
    else:
        clear.append(int(S[i]))
        
number = 0
for i in range(len(clear)):
    pq = int(clear[-1-i])
    number = number + pq * ((10 ** i) % 13) % 13

number = number % 13

num = number
sum = []
L = len(unclear)
for j in range(L):
    sum.append(0)

A = 0
T = 10 ** L
K = 0

while A != T:
    for p in range(L):
        num += sum[p] % 13
        num = num % 13
        
    if num == 5:
        answer += 1
        num = number
    else:
        num = number
    
    A += 1
    
    sum[L-1] += unclear[L-1]
    for i in range(L):
        if sum[L-1-i] == 10 * unclear[L-1-i]:
            sum[L-1-i] = 0
            sum[L-2-i] += unclear[L-2-i]

print(answer)

Submission status: Runtime Error

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

answer = 0
  
clear = []
unclear = []   
for i in range(N):
    if S[i] == "?":
        unclear.append(10 ** (N - i - 1))
        clear.append(0)
    else:
        clear.append(int(S[i]))
        
number = 0
for i in range(len(clear)):
    pq = int(clear[-1-i])
    number = number + pq * ((10 ** i) % 13) % 13

number = number % 13

num = number
print(num)
sum = []
L = len(unclear)
for j in range(L):
    sum.append(0)

A = 0
T = 10 ** L
K = 0

while A != T:
    print(sum)
    for p in range(L):
        num += sum[p] % 13
        num = num % 13
        
    if num == 5:
        answer += 1
        num = number
    else:
        num = number
    
    A += 1
    
    sum[L-1] += unclear[L-1]
    for i in range(L):
        if sum[L-1-i] == 10 * unclear[L-1-i]:
            sum[L-1-i] = 0
            sum[L-2-i] += unclear[L-2-i]

print(answer)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <math.h>
#include <fstream>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
#include <vector>
#include <set>
#include <map>
using namespace std;

int main() {
	string S;
	cin >> S;
	long long int dp[100010][13] = {},len=S.length();
	dp[0][0] = 1;
	for (int i = 1; i <= len; i++)
	{
		int num = S[i - 1] - '0';
		for (int j = 0; j < 13; j++)
		{
			if (num != '?' - '0') {
				dp[i][(j * 10 + num) % 13] += dp[i - 1][j];
			}
			else
			{
				for (int k = 0; k < 10; k++)
				{
					dp[i][(j * 10 + k)%13] += dp[i - 1][j];
				}
			}
		}
		for (int j = 0; j < 13; j++)dp[i][j] %= 1000000007;
	}
	cout << dp[len][5];
}

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <math.h>
#include <fstream>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
#include <vector>
#include <set>
#include <map>
using namespace std;

int main() {
	string S;
	cin >> S;
	long long int dp[100][13] = {},len=S.length();
	dp[0][0] = 1;
	for (int i = 1; i <= len; i++)
	{
		int num = S[i - 1] - '0';
		for (int j = 0; j < 13; j++)
		{
			if (num != '?' - '0') {
				dp[i][(j * 10 + num) % 13] += dp[i - 1][j];
			}
			else
			{
				for (int k = 0; k < 10; k++)
				{
					dp[i][(j * 10 + k)%13] += dp[i - 1][j];
				}
			}
		}
		for (int j = 0; j < 13; j++)dp[i][j] %= 1000000007;
	}
	cout << dp[len][5];
}

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import numpy as np
S = list(input())
q_num = S.count("?")
cnt=0
for i in range(10**q_num):
  temp_S=S.copy()
  i = str(i)
  if len(i)!=q_num:
    i = "".join(list(np.zeros(q_num-len(i)).astype(int).astype(str)) + list(i))
  for num in i:
    temp_S[temp_S.index("?")] = num
  temp_S = int("".join(temp_S))
  if temp_S%13==5:
    cnt+=1
print(cnt%(10**9+7))

Submission status: Runtime Error

Solution code:
import numpy as np
S = list(input())
q_num = S.count("?")
cnt=0
for i in range(10**q_num):
  temp_S=S.copy()
  i = str(i)
  if len(i)!=q_num:
    i = "".join(list(np.zeros(q_num-len(i)).astype(int).astype(str)) + list(i))
  for num in i:
    temp_S[temp_S.index("?")] = num
  temp_S = int("".join(temp_S))
#  print(temp_S)
  if temp_S&13==5:
    cnt+=1
print(cnt%(10**9+7))

Submission status: Runtime Error

Solution code:
import numpy as np
S = list(input())
q_num = S.count("?")
cnt=0
for i in range(10**q_num):
  temp_S=S.copy()
  i = str(i)
  if len(i)!=q_num:
    i = "".join(list(np.zeros(q_num-len(i)).astype(int).astype(str)) + list(i))
  for num in i:
    temp_S[temp_S.index("?")] = num
  temp_S = int("".join(temp_S))
  print(temp_S)
  if temp_S&13==5:
    cnt+=1
print(cnt%(10**9+7))

Submission status: Runtime Error

Solution code:
%%time
import numpy as np

mod=10**9+7
#s=input()
s="?"*10**5


p=[[i*j%13 for i in range(10)] for j in range(13)]
rev=reversed(s)
d=np.array([0 for i in range(13)])
d[0]=1
keep=np.array([0 for _ in range(13)])
mul=1
cal=0
t=np.array([i for i in range(13)])
for v in rev:
    if v!="?":
        cal+=mul*int(v)%13
    else:
        t_d=keep.copy()
        for j in range(1,10):
            t_d[(t+mul*j)%13]+=d
        d+=t_d
        d%=mod
        
    mul*=10
    mul%=13

cal%=13
if cal<=5:
    cal=5-cal
else:
    cal=18-cal
print(d[cal]%mod)
#print(d)
#h=d
#print([i%mod for i in h])

Submission status: Runtime Error

Solution code:
import numpy as np
 
S = input()
MOD = 10**9 + 7
 
# 縦i,横j, 数字k
dp_ = [[0 for j in range(13)] for i in range(len(S)+1)]
dp_[0][0] = 1
dp = np.array(dp_, dtype=int)
 
for i in range(len(S)-1):
    if S[i] == '?':
        for j in range(13):
            for k in range(10):
                dp[i+1][(j*10 + k) % 13] += dp[i][j]
    else:
        for j in range(13):
            dp[i+1][(j * 10 + int(s)) % 13] += dp[i][j]
    for j in range(13):
        dp[i+1][j] %= MOD
    
 
print(dp[-1][5] % MOD)

Submission status: Runtime Error

Solution code:

mod = 10**9+7

table = [1,10,9,12,3,4]
#for i in range(1,len(S)+1):
#	tblpow.append(10*tblpow[i-1]%13)

dp = [0]*13
dp[0] = 1
for i in range(len(S)-1,-1,-1):
	ch = int(S[i]) if S[i]!='?' else -1
	temp = [0]*13
	for d in range(10):
		if ch!=-1 and ch!=d:
			continue
		for m in range(13):
			temp[(d*table[i%6]+m)%13] += dp[m]
	for m in range(13):
		temp[m] %= mod
	dp = temp
print(dp[5])

Submission status: Runtime Error

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

mod = 10**9+7

tblpow = [1]
for i in range(1,len(S)+1):
	tblpow.append(10*tblpow[i-1]%13)
print(tblpow)
1 10 9 12 3 4

dp = [0]*13
dp[0] = 1
for i in range(len(S)-1,-1,-1):
	ch = int(S[i]) if S[i]!='?' else -1
	temp = [0]*13
	for d in range(10):
		if ch!=-1 and ch!=d:
			continue
		for m in range(13):
			temp[(d*tblpow[i]+m)%13] += dp[m]
	for m in range(13):
		temp[m] %= mod
	dp = temp
print(dp[5])

Submission status: Runtime Error

Solution code:
from functools import lru_cache

def main(S):
    con = 10**9 + 7

    @lru_cache(maxsize=1024)
    def get_c(iii):
        return [mm13[iii][j] % 13 for j in l10]

    l10 = list(range(10))
    l13 = list(range(13))
    m13 = {i: {j: (i + j) % 13 for j in l13} for i in l13}
    mm13 = {i: {j: (i * j) % 13 for j in range(11)} for i in range(100)}
    c = []
    iii = 1
    for i in range(len(S)):
        s = S[len(S) - i - 1]
        if s != "?":
            c.append(mm13[iii][int(s)])
        else:
            c.append(get_c(iii))
        iii = mm13[iii][10]

    _tdp = {i: 0 for i in l13}
    it = iter(c)
    pdp = {i: 1 for i in next(it)}
    d = 1
    for v in it:
        tdp = _tdp.copy()
        for r in v:
            for _r, _v in pdp.items():
                tdp[m13[_r][r]] += _v
        if d == 0:
            for i in l13:
                tdp[i] = tdp[i] % con
        d = (d + 1) % 50
        pdp = tdp

    ans = pdp.get(5, 0)
    print(ans % con)

if __name__ == "__main__":
    S = input()
    main(S)

Submission status: Runtime Error

Solution code:
from fastcache import clru_cache

def main(S):
    con = 10**9 + 7

    @clru_cache(maxsize=1024, typed=True)
    def get_c(iii):
        return [(j * iii) % 13 for j in l10]

    l10 = list(range(10))
    l13 = list(range(13))
    m13 = {i: {j: (i + j) % 13 for j in l13} for i in l13}
    c = []
    iii = 1
    for i in range(len(S)):
        s = S[len(S) - i - 1]
        if s != "?":
            c.append([(int(s) * iii) % 13])
        else:
            c.append(get_c(iii))
        iii = (iii * 10) % 13

    _tdp = {i: 0 for i in l13}
    it = iter(c)
    pdp = {i: 1 for i in next(it)}
    d = 1
    for v in it:
        tdp = _tdp.copy()
        for r in v:
            for _r, _v in pdp.items():
                tdp[m13[_r][r]] += _v
        if d == 0:
            for i in l13:
                tdp[i] = tdp[i] % con
        d = (d + 1) % 50
        pdp = tdp

    ans = pdp.get(5, 0)
    print(ans % con)

if __name__ == "__main__":
    S = input()
    main(S)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

mod = 10**9+7

S = input()
S = S[::-1]
#print(S)

# 0~i桁目までの部分文字列において
# (mod 13)がbとなるパターン数を返す
@lru_cache(maxsize=None)
def search(i,rem):
	if i==len(S):
		return 1 if rem==5 else 0
	
	ch = int(S[i]) if S[i]!='?' else -1

	res = 0
	for d in range(10):
		if ch!=-1 and ch!=d:
			continue
		num = d*(10**i)%13
		res += search(i+1,(rem+num)%13)
	return res%mod

print(search(0,0))

Submission status: Runtime Error

Solution code:
from functools import lru_cache

S = input()
S = S[::-1]
#print(S)

# 0~i桁目までの部分文字列において
# (mod 13)がbとなるパターン数を返す
@lru_cache(maxsize=None)
def search(i,rem):
	if i==len(S):
		return 1 if rem==5 else 0
	
	ch = int(S[i]) if S[i]!='?' else -1

	res = 0
	for d in range(10):
		if ch!=-1 and ch!=d:
			continue
		num = d*(10**i)%13
		res += search(i+1,(rem+num)%13)
	return res

total = search(0,0)
print(total%(10**9+7))

Submission status: Runtime Error

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

def memoize(f):
	table = {}
	def func(*args):
		if not args in table:
			table[args] = f(*args)
		return table[args]
	return func

# 0~i桁目までの部分文字列において
# (mod 13)がbとなるパターン数を返す
@memoize
def search(i,rem):
	if i==len(S):
		return 1 if rem==5 else 0
	
	ch = int(S[i]) if S[i]!='?' else -1

	res = 0
	for d in range(10):
		if ch!=-1 and ch!=d:
			continue
		num = d*(10**i)%13
		res += search(i+1,(rem+num)%13)
	return res

total = search(0,0)
print(total%(10**9+7))

Submission status: Runtime Error

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

import sys

sys.setrecursionlimit(10**7)

# Override `input` function because `stdin.readline()` is 10x faster than built-in `input()`
input = sys.stdin.readline


def read_h(typ=int):
    return list(map(typ, input().split()))


def read_v(n, m=1, typ=int):
    return [read_h(typ) if m > 1 else typ(input()) for _ in range(n)]


def main():
    S, = read_h(typ=str)
    n = len(S)

    MOD = 10**9 + 7

    dp = [[0] * 13 for _ in range(10**5)]
    dp[0][0] = 1
    #  print('initial dp:', dp)

    for i, s in enumerate(S):
        c = -1 if s == '?' else ord(s) - ord('0')
        #  print('c:', c)

        for j in range(10):
            if c != -1 and c != j:
                continue

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

            #  print('updated dp:', dp[:])

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

        #  print('final dp:', dp[:])

    res = dp[n][5]
    print(res)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
S = input()
mod = 10 ** 9 + 7

n = len(S)
dp = np.zeros((n, 13))
a = S[-1]
now, pre = 10, 1
x_ = dp[0]
l = [1, 10, 9, 12, 3, 4]
l = [[i * l_ % 13 for i in range(1, 10)] for l_ in l]
li = 1
if a == "?":
    x_[0:10] = 1
else:
    x_[int(a)] = 1
for s, x in zip(S[-2::-1], dp[1:]):
    if s == "?":
        x += x_
        for v in l[li]:
            x[v:] += x_[:-v]
            x[:v] += x_[-v:]
    else:
        if s == "0":
            x += x_
        else:
            x[v:] += x_[:-v]
            x[:v] += x_[-v:]
    x %= mod
    li += 1
    li %= 6
    x_ = x
print(int(dp[-1][5]))

Submission status: Runtime Error

Solution code:
import numpy as np
S = input()
mod = 10 ** 9 + 7

n = len(S)
dp = np.zeros((n, 13))
a = S[-1]
now, pre = 10, 1
x_ = dp[0]
if a == "?":
    x_[0:10] = 1
else:
    x_[int(a)] = 1
for s, x in zip(S[-2::-1], dp[1:]):
    if s == "?":
        for v in range(10):
            w = v * now % 13
            x[w:13] += x_[:13 - w]
            x[:w] += x_[13 - w:]
    else:
        v = int(s) * now % 13
        x[w:13] = x_[:13 - w]
        x[:w] = x_[13 - w:]
    x %= mod
    now, pre = (now - pre) % 13, now
    x_ = x
print(int(dp[-1][5]))

Submission status: Runtime Error

Solution code:
d=[0]*13
d[0]=1
s=input()
for k,t in enumerate(s[::-1]):
    if t=='?':
        d2=[0]*13
        for i in range(10):
            u=i*pow(10,d,13)
            for i in range(13):
                d2[(i+u)%13]+=d[i]
    else:
        u=int(t)*pow(10,d,13)
        d2=[0]*13
        for i in range(13):
            d2[(i+u)%13]+=d[i]
    for i in range(13):
        d[i]=d2[i]%(10**9+7)
print(d[5])

Submission status: Runtime Error

Solution code:
from sys import stdin

def main():
    s = [int(x) if x != "?" else "?" for x in stdin.readline().rstrip()]

    dp = [1] + [0]*12
    mul = 1
    mod = 10 ** 9 + 7
    s.reverse()

    for i in (range(0,len(s))):
        next_dp = [0]*13
        if s[i] == "?":
            for k in range(0, 10):
                for j in range(0, 13):
                    next_dp[(k*mul+j)%13] += dp[j]
                    next_dp[(k*mul+j)%13] %= mod

        else:
            k = s[i]
            for j in range(0, 13):
                    next_dp[k*mul+j)%13] += dp[j]
                    next_dp[k*mul+j)%13] %= mod

        mul = mul * 10 % 13
        dp = next_dp

    print(dp[5])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

MOD = 1000000007
S = input()[::-1]

a = 10 ** np.arange(6) % 13
b = np.tile(np.arange(10),(6, 1))
c = a * b.T % 13
c = c.T
f = np.zeros((6, 13, 13), dtype=np.int64)
for i in range(6):
    f[i, 0, c[i]] = 1
    for j in range(12):
        f[i, j + 1] = np.roll(f[i, j], 1)

prev = np.zeros(13, dtype=np.int64)
prev[0] = 1
digit = 0

for i, c in enumerate(S):
    k = i % 6
    if c == '?':
        cur = prev @ f[k] % MOD
        prev, cur = cur, prev
    else:
        digit += a[k] * (ord(c) - ord('0'))

m = (5 - digit) % 13
print(prev[m])

Submission status: Runtime Error

Solution code:
def main():
    S = input()
    con = 10**9 + 7

    def get_mod(S):
        c = {}
        iii = 1
        for i in range(len(S)):
            if S[len(S) - i - 1] != "?":
                c[i] = {(int(S[len(S) - i - 1]) * iii) % 13: 1}
                iii *= 10
                iii %= 13
                continue
            c[i] = {(j * iii) % 13: 1 for j in range(0, 10)}
            iii *= 10
            iii %= 13
        return c
    c = get_mod(S)

    def get_tdp(pdp):
        tdp = {i: 0 for i in range(13)}
        for r in v.keys():
            for _r, _v in pdp.items():
                tdp[(_r + r) % 13] += _v
        for i in range(13):
            tdp[i] %= con
        return tdp

    it = iter(c.items())
    pdp = next(it)[-1]
    for k, v in it:
        pdp = get_tdp(pdp)

    ans = pdp[5]
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

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

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

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

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

Submission status: Runtime Error

Solution code:
def main():
  s = ''.join(reversed(input()))
  multiplier = 1
  divisor = 10 ** 9 + 7
  list10 = list(range(10))
  list13 = list(range(13))
  p = [0 for i in list13]
  np = [0 for i in list13]
  rt = [i % 13 for i in range(120)]
  p[0] = 1
  for i in range(len(s)):
    multiplier = rt[10 * multiplier]
    if s[i] != '?':
      r = rt[int(s[i]) * multiplier]
      for j in list13:
        np[rt[j + r]] = p[j]
    else:
      r = 0
      for j in list10:
        for k in list13:
          np[rt[k + r]] += p[k]
        r = rt[r + multiplier]
    for j in list13:
      p[j] = np[j] % divisor
      np[j] = 0
  print(p[5])
main()