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: Time Limit Exceeded

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
def main():
    s=list(input())
    mod=10**9+7
    K=modinv(10,13)
    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

    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)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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
K=modinv(10,13)
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

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: Time Limit Exceeded

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()
L=len(S)
s=[0 for i in range(L)]
for i in range(L):
    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(L)]
#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,L):
    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[L-1][5]%mod)

Submission status: Time Limit Exceeded

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
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][((k-j)*K)%13]
        dp[i][k]=dp[i][k]%mod
    else:
        number=int(s[i])
        for k in range(13):
            dp[i][k]=dp[i-1][((k-number)*K)%13]%mod
print(dp[len(s)-1][5]%mod)

Submission status: Time Limit Exceeded

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
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][((k-j)*K)%13]
        dp[i][k]=dp[i][k]%mod
    else:
        number=int(s[i])
        for k in range(13):
            dp[i][k]=dp[i-1][((k-number)*K)%13]%mod
print(dp[len(s)-1][5]%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines 
MOD = 10**9+7

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

dp[0][0] = 1
for dgt in range(N):
  for mo in range(13):
    if S[dgt] == "?":
      for nxt in range(10):
        ind = (mo*10 + nxt) % 13
        dp[dgt+1][ind] += dp[dgt][mo]
        #dp[dgt+1][ind] %= MOD
    else:
      ind = (mo*10 + int(S[dgt])) % 13
      dp[dgt+1][ind] += dp[dgt][mo]
      #dp[dgt+1][ind] %= MOD
print(dp[N][5]%MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines 
MOD = 10**9+7

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

dp[0][0] = 1
for dgt in range(N):
  for mo in range(13):
    if S[dgt] == "?":
      for nxt in range(10):
        ind = (mo*10 + nxt) % 13
        dp[dgt+1][ind] += dp[dgt][mo]
        dp[dgt+1][ind] %= MOD
    else:
      ind = (mo*10 + int(S[dgt])) % 13
      dp[dgt+1][ind] += dp[dgt][mo]
      dp[dgt+1][ind] %= MOD
print(dp[N][5])

Submission status: Time Limit Exceeded

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

#dp[i][j]...i桁目までで余りがj
dp=[[0 for _ in range(13)] for _ in range(len(s)+1)]
dp[0][0]=1

for i in range(0,len(s)):
    if s[i]=='?':
        for j in range(13):
            for x in range(10):
                dp[i+1][(j*10+x)%13]+=dp[i][j]
                dp[i+1][(j*10+x)%13]%=mod
    else:
        x=int(s[i])
        for j in range(13):
            dp[i+1][(j*10+x)%13]+=dp[i][j]
            dp[i+1][(j*10+x)%13]%=mod
    
print(dp[len(s)][5])

Submission status: Time Limit Exceeded

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

#dp[i][j]...i桁目までで余りがj
dp=[[0 for _ in range(13)] for _ in range(len(s)+1)]
dp[0][0]=1

for i in range(0,len(s)):
    if s[i]=='?':
        for j in range(13):
            for x in range(10):
                dp[i+1][(j*10+x)%13]+=dp[i][j]
    else:
        x=int(s[i])
        for j in range(13):
            dp[i+1][(j*10+x)%13]+=dp[i][j]
    
print(dp[len(s)][5]%mod)

Submission status: Time Limit Exceeded

Solution code:
S=input()
N=len(S)
X=10**9+7
d=[0 for i in range(13)]
p=[0 for i in range(13)]
if S[N-1]=='?':
    for i in range(0,10):
        d[i]=1
else:
    d[int(S[N-1])]=1
for i in range(N-1):
    if S[N-i-2]=='?':
        for j in range(10):
            A=(10**(i+1))%13
            for k in range(13):
                a=A*j
                p[(a+k)%13]=(p[(a+k)%13]+d[k])%X
    else:
        a=(int(S[N-i-2])*10**(i+1))%13
        for k in range(13):
            p[(a+k)%13]=d[k]
    for i in range(13):
        d[i]=p[i]
        p[i]=0
print(d[5])

Submission status: Time Limit Exceeded

Solution code:
S=input()
N=len(S)
X=10**9+7
dp=[[0 for i in range(13)] for i in range(N)]
d=[0 for i in range(13)]
p=[0 for i in range(13)]
if S[N-1]=='?':
    for i in range(0,10):
        d[i]=1
else:
    d[int(S[N-1])]=1
for i in range(N-1):
    if S[N-i-2]=='?':
        for j in range(10):
            A=(10**(i+1))%13
            for k in range(13):
                a=A*j
                p[(a+k)%13]=(p[(a+k)%13]+d[k])%X
    else:
        a=(int(S[N-i-2])*10**(i+1))%13
        for k in range(13):
            p[(a+k)%13]=d[k]
    for i in range(13):
        d[i]=p[i]
        p[i]=0
print(d[5])

Submission status: Time Limit Exceeded

Solution code:
S=input()
N=len(S)
X=10**9+7
dp=[[0 for i in range(13)] for i in range(N)]
if S[N-1]=='?':
    for i in range(0,10):
        dp[0][i]=1
else:
    dp[0][int(S[N-1])]=1
for i in range(N-1):
    if S[N-i-2]=='?':
        for j in range(10):
            A=(10**(i+1))%13
            for k in range(13):
                a=A*j
                dp[i+1][(a+k)%13]=(dp[i+1][(a+k)%13]+dp[i][k])%X
    else:
        a=(int(S[N-i-2])*10**(i+1))%13
        for k in range(13):
            dp[i+1][(a+k)%13]=dp[i][k]
print(dp[N-1][5])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from math import pow
S = input()
S = list(S)
S.reverse()
l = len(S)
dp =[ [0] * 13 for _ in range(l + 1)]
dp[0][0] = 1
MOD = 10 ** 9 + 7
keta = 1
for k,c in enumerate(S):
    if c == "?":
        for i in range(0,10): # ? に入る候補達
            for amari in range(0, 13):
                next_amari = (amari + i * keta ) % 13
                dp[k + 1][next_amari] += (dp[k][amari] )
                dp[k + 1][next_amari] %= MOD
    else:
        i = int(c)
        for amari in range(0,13):
            next_amari = (amari + i * keta ) % 13
            dp[k + 1][ next_amari] += (dp[k][amari])
            dp[k + 1][next_amari] %= MOD

    keta *= 10   
    # keta %= MOD なんで？


print(dp[l][5])

Submission status: Time Limit Exceeded

Solution code:
s=input()
mod=10**9+7
cnt=0
for i in range(1,10**len(s)):
    temp=i
    if i%13==5:
        temp_str='0'*(len(s)-len(str(temp)))+str(temp)
        for x, y in zip(s, temp_str):
            if x != y and x!='?': break
        else:
            cnt += 1
print(cnt % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

S = input()

dp = [[0] * 13 for i in range(len(S)+1)]

dp[0][0] = 1

for i in range(len(S)):
    if S[i] == "?":
        c = -1
    else:
        c = int(S[i])
    for j in range(0, 10):
        if c != -1 and c != j:
            continue
        for k in range(0, 13):
            # dp[i+1][(10*k + j) % 13] = (dp[i+1][(10*k+j) % 13] + dp[i][k]) % mod
            dp[i+1][(10*k+j) % 13] = (dp[i+1][(10*k+j) % 13] + dp[i][k]) % mod
print(dp[len(S)][5])

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

S = input()

dp = [[0] * 13 for i in range(len(S)+1)]

dp[0][0] = 1

for i in range(len(S)):
    if S[i] == "?":
        c = -1
    else:
        c = int(S[i])
    for j in range(0, 10):
        if c != -1 and c != j:
            continue
        for k in range(0, 13):
            # dp[i+1][(10*k + j) % 13] = (dp[i+1][(10*k+j) % 13] + dp[i][k]) % mod
            dp[i+1][(10*k+j) % 13] += dp[i][k]
print(dp[len(S)][5] % mod)

Submission status: Time Limit Exceeded

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

l = len(s)
s = [int(e) if e != "?" else -1 for e in s]
dp = [[0] * 13 for _ in range(l + 1)]
dp[0][0] = 1

for i in range(l):
	for k in range(10):
		if s[i] == -1 or s[i] == k:
			for j in range(13):
				nj = (j * 10 + k) % 13
				dp[i+1][nj] += dp[i][j]
				dp[i+1][nj] %= mod

ans = dp[l][5]
print(ans)

Submission status: Time Limit Exceeded

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

    mod13=[1]*(10**5+1)
    for i in range(10**5):
        mod13[i+1]=mod13[i]*10%13
    
    s=list(input())[::-1]
    l=len(s)
    
    dp=[[0]*13 for _ in range(1+l)]

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

    for i in range(1,l):
        if s[i]=='?':
            for j in range(13):
                for num in range(10):
                    t=(j+mod13[i]*num)%13
                    dp[i+1][t]+=dp[i][j]
                    dp[i+1][t]%=MOD
        
        else:
            num=int(s[i])
            for j in range(13):
                t=(j+mod13[i]*num)%13
                dp[i+1][t]+=dp[i][j]
                dp[i+1][t]%=MOD
    
    print(dp[-1][5])
 
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

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)) % 13] += dp[i][j]
            dp[i + 1][(10 * j + int(v)) % 13] %= mod
            continue
        for k in range(10):
            x = (10 * j + k) % 13
            dp[i + 1][x] += dp[i][j]
            dp[i + 1][x] %= mod

print(dp[-1][5])

Submission status: Time Limit Exceeded

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):
        for k in range(10):
            x = (10 * j + k) % 13
            if v != "?":
                if int(v) == k:
                    dp[i + 1][x] += dp[i][j]
                    dp[i + 1][x] %= mod
                else:
                    dp[i + 1][x] += 0
            else:
                dp[i + 1][x] += dp[i][j]
                dp[i + 1][x] %= mod

print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
mod = 10**9+7
dp = [0]*13
dp[0] = 1
for i,d in enumerate(s):
	_dp=[0]*13
	if d=="?":
		for x in range(10):
			for y in range(13):
				_dp[(y*10+x)%13] += dp[y]
	else:
		d = int(d)
		for y in range(13):
			_dp[(y*10+d)%13] += dp[y]
	for j in range(13):
		_dp[j] %= mod
	dp=_dp
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import sys
s= sys.stdin.readline().strip()
mod=10**9+7
n=13
dp=[0]*n
mul=1
dp[0]=1
for c in reversed(s):
  ndp=[0]*n
  if c=='?':
    for k in range(10):
      k*=mul
      for j in range(n):
        t=(k+j)%n
        ndp[t]+=dp[j]
        ndp[t]%=mod
  else:
    k=int(c)*mul
    for j in range(n):
      t=(k+j)%n
      ndp[t]+=dp[j]
      ndp[t]%=mod
  mul*=10
  mul%=n
  dp=ndp
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import sys
s= sys.stdin.readline().strip()
mod=10**9+7
n=13
dp=[0]*n
mul=1
dp[0]=1
for c in reversed(s):
  ndp=[0]*n
  if c=='?':
    for k in range(10):
      for j in range(n):
        ndp[(k*mul+j)%n]+=dp[j]
        ndp[(k*mul+j)%n]%=mod
  else:
    k=int(c)
    for j in range(n):
      ndp[(k*mul+j)%n]+=dp[j]
      ndp[(k*mul+j)%n]%=mod
  mul*=10
  mul%=n
  dp=ndp
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
s=input()[::-1]
mod=10**9+7
n=13
dp=[0]*n
mul=1
dp[0]=1
for c in s:
  ndp=[0]*n
  if c=='?':
    for k in range(10):
      for j in range(n):
        ndp[(k*mul+j)%n]=(ndp[(k*mul+j)%n]+dp[j])%mod
        #ndp[(k*mul+j)%n]%=mod
  else:
    k=int(c)
    for j in range(n):
      ndp[(k*mul+j)%n]=(ndp[(k*mul+j)%n]+dp[j])%mod
      #ndp[(k*mul+j)%n]%=mod
  mul*=10
  mul%=n
  dp=ndp
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
s=input()[::-1]
mod=10**9+7
n=13
dp=[0]*n
mul=1
dp[0]=1
for c in s:
  ndp=[0]*n
  if c=='?':
    for k in range(10):
      for j in range(n):
        ndp[(k*mul+j)%n]+=dp[j]
        ndp[(k*mul+j)%n]%=mod
  else:
    k=int(c)
    for j in range(n):
      ndp[(k*mul+j)%n]+=dp[j]
      ndp[(k*mul+j)%n]%=mod
  mul*=10
  mul%=n
  dp=ndp
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def main():
    S=input()
    dp=np.zeros((len(S)+1,13),dtype=int)
    dp[0][0]=1
    mod=10**9+7
    for i in range(1,len(S)+1):
        for a in range(13):
            if S[i-1]=="?":
                if a*10%13<(a*10+10)%13:
                    dp[i][a*10%13:(a*10+10)%13]+=dp[i-1][a]
                    dp[i][a*10%13:(a*10+10)%13]%=mod
                else:
                    dp[i][a*10%13:]+=dp[i-1][a]
                    dp[i][a*10%13:]%=mod
                    dp[i][:(a*10+10)%13]+=dp[i-1][a]
                    dp[i][:(a*10+10)%13]%=mod
            else:
                dp[i][(a*10+int(S[i-1]))%13]+=dp[i-1][a]
                dp[i][(a*10+int(S[i-1]))%13]%=mod
    print(dp[len(S)][5])
"""
    for i in range(1,len(S)+1):
        for a in range(13):
            if S[i-1]=="?":
                for n in range(10):
                    dp[i][(a*10+n)%13]+=dp[i-1][a]
            else:
                dp[i][(a*10+int(S[i-1]))%13]+=dp[i-1][a]
"""
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
s.reverse()
n = len(s)
mod = 10**9+7
#dp[i][j] := 下からi桁目まで決めたとき、13で割った余りがjの個数
dp = [[0 for i in range(13)] for j in range(n+1)]
dp[0][0] = 1
for i in range(n):
    for j in range(13):
        char = s[i]
        if char == '?':
            for k in range(10):
                #i+1桁目をkにする
                tmp = (k * pow(10, i)) % 13
                dp[i+1][(j + tmp) % 13] += dp[i][j]
                dp[i+1][(j + tmp) % 13] %= mod
        else:
            x = int(char)
            tmp = (x * pow(10, i)) % 13
            dp[i+1][(j + tmp) % 13] += dp[i][j]
            dp[i+1][(j + tmp) % 13] %= mod
print(dp[n][5])

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
s.reverse()
n = len(s)
mod = 10**9+7
#dp[i][j] := 下からi桁目まで決めたとき、13で割った余りがjの個数
dp = [[0 for i in range(13)] for j in range(n+1)]
dp[0][0] = 1
for i in range(n):
    for j in range(13):
        char = s[i]
        if char == '?':
            for k in range(10):
                #i+1桁目をkにする
                tmp = (k * (10 ** i)) % 13
                dp[i+1][(j + tmp) % 13] += dp[i][j]
                dp[i+1][(j + tmp) % 13] %= mod
        else:
            x = int(char)
            tmp = x * (10**i)
            dp[i+1][(j + tmp) % 13] += dp[i][j]
            dp[i+1][(j + tmp) % 13] %= mod
print(dp[n][5])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

MAX = 10**9 + 7

def main():
  s = input().strip()
  p = 13
  dp = [[0]*p for _ in range(len(s))]
  if s[-1] == '?':
    dp[0][:10] = [1] * 10
  else:
    dp[0][int(s[-1])] = 1
  for i, c in enumerate(s[::-1][1:], 1):
    if c == '?':
      for c in range(10):
        for j in range(p):
          dp[i][(int(c) * (10 ** i) + j) % p] += (dp[i-1][j] % MAX)
    else:
      for j in range(p):
        dp[i][(int(c) * (10 ** i) + j) % p] += (dp[i-1][j] % MAX) 
  print(dp[-1][5] % MAX)
  
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
dp = [[0]*13 for i in range(n+5)]
dp[0][0] = 1
mod = 10**9+7
for i in range(n):
	    for j in range(13):
	    	    if s[i] != '?':
	    	    	    x = int(s[i])
	    	    	    ni = i+1
	    	    	    nj = (j*10+x)%13
	    	    	    dp[ni][nj] += dp[i][j]
	    	    	    dp[ni][nj]%= mod
	    	    	    continue
	    	    for d in range(10):
	    	    	    ni = i+1
	    	    	    nj = (j*10+d)%13
	    	    	    dp[ni][nj] += dp[i][j]
	    	    	    dp[ni][nj]%= mod
print(dp[n][5])

Submission status: Time Limit Exceeded

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)

dp = [[0]*13 for _ in range(len(listStr)+1)]
dp[0][0] = 1 #上から回すので、文字列の1個上の桁を0としてベースにしている

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)

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

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)

# del listStr[len(listStr)-1]
listStr.reverse()

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

INF = 10 ** 9 + 7

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: Time Limit Exceeded

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)

del listStr[len(listStr)-1]
listStr.reverse()

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

INF = 10 ** 9 + 7

for i in range(len(listStr)):
    if i ==0:
        keta = 1
    else:
        keta = pow(10, i)

    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 * ordinal) + j) % 13)] %= INF
    else:
        k = int(listStr[i])
        for j in range(13):
            dp[i + 1][int(((k*keta)%13 + j) % 13)] += dp[i][j]
            # dp[i + 1][int(((k*ordinal) + j) % 13)] %= INF


ans = dp[len(listStr)][5] % INF
print(ans)