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

dp = [0] * 13
dp[0] = 1

for s in S:
    prev = dp
    dp = [0] * 13
    if s == '?':
        add = range(10)
    else:
        add = [int(s)]
    for i in range(13):
        for a in add:
            dp[(10*i+a)%13] += prev[i]
    dp = [x%MOD for x in dp]
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
N = len(S)
dp = [[0] * 13 for _ in range(N+1)]
MOD = 10**9 + 7
s = S[0]
if s=='?':
    for k in range(10):
        dp[0][k] = 1
else:
    dp[0][int(s)] = 1
 

for i in range(1,N):
    s = S[i]
    if s=='?':
        for j in range(13):
            for k in range(10):
                tmp = (j*10 + k)%13
                dp[i][tmp] += dp[i-1][j]
                dp[i][tmp] %= MOD
    else:
        for j in range(13):
            tmp = (j*10 + int(s))%13
            dp[i][tmp] += dp[i-1][j]
            dp[i][tmp] %= MOD
            
print(dp[N-1][5])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
n = len(s)
s.reverse()
dp = [[0 for i in range(13)] for j in range(n)]
if s[0] == "?":
    for i in range(10):
        dp[0][i] = dp[0][i] + 1
else:
    s0 = int(s[0])
    dp[0][s0] = dp[0][s0] + 1
for i in range(1,n):
    if s[i] != "?":
        s1 = int(s[i])
        for j in range(13):
            k = (s1*(10**i))%13
            dp[i][(j+k)%13] = dp[i-1][j]
    else:
        p = (10**i) % 13
        for j in range(13):
            for x in range(10):
                k = (x*p)%13
                dp[i][(j+k)%13] += dp[i-1][j]
            dp[i] = [dp[i][j]%(10**9 + 7) for j in range(13)]
print(dp[n-1][5])

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
S = input()


table = {}
pairs = [[((i*10 + j)%13, i) for i in range(13)] for j in range(13)]
mod = 10**9 + 7
for i in range(13):
    table[i] = tuple((i + j*13)//10 for j in range(10))

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

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

for i in range(1, len(S)):
    s = S[i]
    if s == "?":
        for j in range(13):
            for k in table[j]:
                dp[i][j] += dp[i-1][k] % mod
    else:
        s = int(s)
        for pair in pairs[s]:
            dp[i][pair[0]] = dp[i-1][pair[1]] % mod

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
dp = [0] * 13
dp[0] = 1
for c in s:
    old = dp.copy()
    for i in range(13):
        dp[i] = 0
    if c == '?':
        for n in range(10):
            for i in range(13):
                dp[(i * 10 + n) % 13] += old[i]
    else:
        n = int(c)
        for i in range(13):
            dp[(i * 10 + n) % 13] += old[i]
    for i in range(13):
        dp[i] %= 10 ** 9 + 7
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7

S = input()

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

for i, s in enumerate(S):
    c = -1 if s == "?" else int(s)
    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]
    for j in range(13):
        dp[i + 1][j] %= mod

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():  
    S = list(input())
    S.pop()
    length=len(S)
    dp = [0]*13
    dp[0]=1
    mul=1
    mod=1000000007
    for i in range(1,length+1):
        next_dp = [0]*13
        for j in range(13):
            if S[length-i] == "?":
                for k in range(10):
                    j_sub=(j+k*mul)%13
                    next_dp[j_sub]+=dp[j]
                    next_dp[j_sub]%=mod
            else:
                j_sub=(j+int(S[length-i])*mul)%13
                next_dp[j_sub]+=dp[j]
                next_dp[j_sub]%=mod
        dp=next_dp
        mul=mul*10%13
    print(dp[5]%1000000007)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():  
    S = list(input())
    S.pop()
    length=len(S)
    dp = [0]*13
    dp[0]=1
    mul=1
    mod=1000000007
    for i in range(1,length+1):
        next_dp = [0]*13
        for j in range(13):
            if S[length-i] == "?":
                for k in range(10):
                    j_sub=(j+k*mul)%13
                    next_dp[j_sub]+=dp[j]
                    next_dp[j_sub]%=mod
            else:
                j_sub=(j+int(S[length-i])*mul)%13
                next_dp[j_sub]+=dp[j]
                next_dp[j_sub]%=mod
        dp=next_dp
        mul=mul*10
    print(dp[5]%1000000007)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

s = [int(x) if x != "?" else -1 for x in input().strip()]
n = len(s)
m = 10**9+7
dp = [0] * 26
mul = 1

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

for i in range(2, n + 1):
    mul *= 10

    if s[-i] == -1:
        for j in range(10):
            rem = (j * mul) % 13
            for k in range(13):
                if dp[k] != 0:
                    a = (k + rem) % 13
                    dp[a + 13] += dp[k]%m
    else:
        rem = (s[-i] * mul) % 13
        for k in range(13):
            if dp[k] != 0:
                a = (k + rem) % 13
                dp[a + 13] += dp[k]%m
    dp[:13] = dp[13:26]
    dp[13:26] = [0]*13
print(dp[5]%m)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
    
S = list(input())
length=len(S)
dp = [[0]*13 for _ in range(length)]
dp[0][0]=1
mul=1
for i in range(1,length):
    for j in range(13):
        if dp[i-1][j] != 0:
            if S[length-i-1] == "?":
                for k in range(10):
                    j_sub = j+k*mul%13
                    if j_sub > 12: j_sub-=13
                    dp[i][j_sub]+=dp[i-1][j]
            else: 
                j_sub = j+int(S[length-i-1])*mul%13
                if j_sub > 12: j_sub-= 13
                dp[i][j_sub]+=dp[i-1][j]
    mul=mul*10
print(dp[length-1][5]%1000000007)

Submission status: Time Limit Exceeded

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

s = input().strip()
n = len(s)
mod = 10**9+7
dp = [0] * 13
mul = 1

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

for i in range(2, n + 1):
    next_dp = [0]*13
    mul *= 10

    if s[-i] == "?":
        for j in range(10):
            rem = (j * mul) % 13
            for k in range(13):
                if dp[k] != 0:
                    a = (k + rem) % 13
                    next_dp[a] += dp[k]
    else:
        rem = (int(s[-i]) * mul) % 13
        for k in range(13):
            if dp[k] != 0:
                a = (k + rem) % 13
                next_dp[a] += dp[k]
    dp = copy.deepcopy(next_dp)
print(int(dp[5] % mod))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
#sys.setrecursionlimit(1000000)
S = list(input())
length=len(S)
dp = [[0]*13 for _ in range(length)]
dp[0][0]=1
mul = 1
for i in range(length-1):
    if S[length-i-2] == "?":
        for k in range(10):
            for j in range(13):
                j_sub = j-k*mul%13
                if j_sub < 0: j_sub+= 13
                dp[i+1][j]+=dp[i][j_sub]
    else:
        for j in range(13):
            j_sub = j-int(S[length-i-2])*mul%13
            if j_sub < 0: j_sub+= 13
            dp[i+1][j]+=dp[i][j_sub]
    mul=mul*10
print(dp[length-1][5]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
#sys.setrecursionlimit(1000000)
S = list(input())
length=len(S)
dp = [[0]*13 for _ in range(length)]
dp[0][0]=1
for i in range(length-1):
    if S[length-i-2] == "?":
        for k in range(10):
            for j in range(13):
                j_sub = j-k*10**i%13
                if j_sub < 0: j_sub+= 13
                dp[i+1][j]+=dp[i][j_sub]
    else:
        for j in range(13):
            j_sub = j-int(S[length-i-2])*10**i%13
            if j_sub < 0: j_sub+= 13
            dp[i+1][j]+=dp[i][j_sub]
print(dp[length-1][5]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
    
S = list(input())
length=len(S)
dp = [[0 for _ in range(13)] for _ in range(length)]
dp[0][0]=1
for i in range(length-1):
    if S[length-i-2] == "?":
        for k in range(10):
            for j in range(13):
                j_sub = j-k*10**i%13
                if j_sub < 0: j_sub+= 13
                dp[i+1][j]+=dp[i][j_sub]
    else:
        for j in range(13):
            j_sub = j-int(S[length-i-2])*10**i%13
            if j_sub < 0: j_sub+= 13
            dp[i+1][j]+=dp[i][j_sub]
print(dp[length-1][5]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
import numpy

S = input()
length=len(S)
dp = numpy.zeros(26)
dp[0]=1
for i in range(length-1):
    for j in range(13):
        if S[length-i-2] == "?":
            for k in range(10):
                j_sub = j-k*10**i%13
                if j_sub < 0: j_sub+= 13
                dp[j+13]+=dp[j_sub]%1000000007
        else: 
            j_sub = j-int(S[length-i-2])*10**i%13
            if j_sub < 0: j_sub+= 13
            dp[j+13]+=dp[j_sub]%1000000007
    dp[0:13] = dp[13:]
    dp[13:]=0
#print(int(dp%1000000007))
print(int(dp[5]%1000000007))

Submission status: Time Limit Exceeded

Solution code:
S = input()

table = {
    0: 0,
    1: 4,
    2: 8,
    3: 12,
    4: 3,
    5: 7,
    6: 11,
    7: 2,
    8: 6,
    9: 10,
    10: 1,
    11: 5,
    12: 9
}

last = [0 for _ in range(13)]
flag = True
hoge = [0, 4, 5, 6, 7, 8, 9, 10, 11, 12]

for c in S:
    tmp = [0 for _ in range(13)]
    if flag:
        if c == '?':
            tmp = [1 if i < 10 else 0 for i in range(13)]
        elif c == '0':
            continue
        else:
            tmp = [1 if i == int(c) else 0 for i in range(13)]
        
        flag = False
        last = tmp
        continue

    if c == '?':
        tmp[0] = sum([last[table[j]] for j in hoge])
        tmpsum = tmp[0]

        for j in range(1, 13):
            tmp[j] = tmpsum + last[table[j]] - last[table[(j + 3) % 13]]
            tmpsum = tmp[j]

    else:
        c = int(c)
        for j in range(13):
            tmp[j] = last[table[(j-c) % 13]]
        
    last = tmp

print(last[5] % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
S = input()

table = {
    0: 0,
    1: 4,
    2: 8,
    3: 12,
    4: 3,
    5: 7,
    6: 11,
    7: 2,
    8: 6,
    9: 10,
    10: 1,
    11: 5,
    12: 9
}

last = [0 for _ in range(13)]
flag = True
hoge = [0, 4, 5, 6, 7, 8, 9, 10, 11, 12]

for c in S:
    tmp = [0 for _ in range(13)]
    if flag:
        if c == '?':
            tmp = [1 if i < 10 else 0 for i in range(13)]
        elif c == '0':
            continue
        else:
            tmp = [1 if i == int(c) else 0 for i in range(13)]
        
        flag = False
        last = tmp
        continue

    if c == '?':
        tmp[0] = sum([last[table[j]] for j in hoge])

        for j in range(1, 13):
            tmp[j] = tmp[j-1] + last[table[j]] - last[table[(j + 3) % 13]]

    else:
        c = int(c)
        for j in range(13):
            tmp[j] = last[table[(j-c) % 13]]
        
    last = tmp

print(last[5] % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
S = input()

table = {
    0: 0,
    1: 4,
    2: 8,
    3: 12,
    4: 3,
    5: 7,
    6: 11,
    7: 2,
    8: 6,
    9: 10,
    10: 1,
    11: 5,
    12: 9
}

last = [0 for _ in range(13)]
flag = True

for c in S:
    tmp = []
    if flag:
        if c == '?':
            tmp = [1 if i < 10 else 0 for i in range(13)]
        elif c == '0':
            continue
        else:
            tmp = [1 if i == int(c) else 0 for i in range(13)]
        
        flag = False
        last = tmp
        continue

    if c == '?':
        tmp = [0 for _ in range(13)]
        for i in range(10):
            for j in range(13):
                tmp[j] += last[table[(j-i) % 13]]

    else:
        c = int(c)
        for j in range(13):
            tmp.append(last[table[(j-c) % 13]])
        
    last = tmp

print(last[5] % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

S = list(input())
length=len(S)
dp = [[0 for _ in range(13)] for _ in range(length)]
dp[0][0]=1
for i in range(length-1):
    for j in range(13):
        if S[length-i-2] == "?":
            for k in range(10):
                j_sub = j-k*10**i%13
                if j_sub < 0: j_sub+= 13
                dp[i+1][j]+=dp[i][j_sub]
        else: 
            j_sub = j-int(S[length-i-2])*10**i%13
            if j_sub < 0: j_sub+= 13
            dp[i+1][j]+=dp[i][j_sub]
print(dp[length-1][5]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

S = list(input())
S.pop()
length=len(S)
dp = [[0 for _ in range(13)] for _ in range(length+1)]
dp[0][0]=1
for i in range(length):
    for j in range(13):
        if S[length-i-1] == "?":
            for k in range(10):
                j_sub = j-k*10**i%13
                if j_sub < 0: j_sub+= 13
                dp[i+1][j]+=dp[i][j_sub]
        else: 
            j_sub = j-int(S[length-i-1])*10**i%13
            if j_sub < 0: j_sub+= 13
            dp[i+1][j]+=dp[i][j_sub]
print(dp[length][5]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

S = list(input())
S.pop()
length=len(S)
dp = [[0 for _ in range(13)] for _ in range(length+1)]
dp[0][0]=1
for i in range(length):
    for j in range(13):
        if S[length-i-1] == "?":
            for k in range(10):
                j_sub = j-k*10**i%13
                if j_sub < 0: j_sub+= 13
                dp[i+1][j]+=dp[i][j_sub]%1000000007
        else: 
            j_sub = j-int(S[length-i-1])*10**i%13
            if j_sub < 0: j_sub+= 13
            dp[i+1][j]+=dp[i][j_sub]%1000000007
print(dp[length][5]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
S = input()
LS = len(S)
dp = [[0] * 13 for _ in range(LS+1)]
dp[0][0] = 1

for k in range(LS):
    #prev = [x for x in dp]
    #dp = [0] * 13
    s = S[k]
    if s == '?':
        add = range(10)
    else:
        add = [int(s)]
    for i in range(13):
        for a in add:
            dp[k+1][(i*10+a)%13] += dp[k][i]
    dp[k+1] = [x % MOD for x in dp[k+1]]
print(dp[LS][5])

Submission status: Time Limit Exceeded

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

dp = [0] * 13
dp[0] = 1

for s in S:
  prev = [x for x in dp]
  dp = [0] * 13
  if s == '?':
    add = range(10)
  else:
    add = [int(s)]
  for i in range(13):
    for x in add:
      dp[(10*i+x)%13] += prev[i]
  dp = [x % MOD for x in dp]
  
print(dp[5])

Submission status: Time Limit Exceeded

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

dp = [0] * 13
dp[0] = 1

for s in S:
    prev = [x for x in dp]
    dp = [0] * 13
    if s == '?':
        add = range(10)
    else:
        add = [int(s)]
    for i in range(13):
        for a in add:
            dp[(i*10+a)%13] += prev[i]
    dp = [x % MOD for x in dp]
print(dp[5])

Submission status: Time Limit Exceeded

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

dp = [0] * 13
dp[0] = 1

for s in S:
    prev = dp
    dp = [0] * 13
    if s == '?':
        add = range(10)
    else:
        add = [int(s)]
    for i in range(13):
        for a in add:
            dp[(i*10+a)%13] += prev[i]
    dp = [x % MOD for x in dp]
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
dp = [1]+[0]*12
M = 10**9+7
lens = len(s)
mods = [4,1,10,9,12,3]

for i in range(1,lens+1):
  if s[-i] == '?':
    m = mods[i%6]
    dp = [sum(dp[(j-(m*k))%13] for k in range(10))%M for j in range(13)]  
  else:
    m = mods[i%6]*int(s[-i])
    dp = [dp[(j-m)%13] for j in range(13)]
print(dp[5]%M)

Submission status: Time Limit Exceeded

Solution code:
S = [int(x) if x != '?' else - 1 for x in input()]
le=len(S)

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

i=0
for k in S:
    if k==-1:
        for s in range(10):
            for j in range(13):
                dp[i + 1][(s + j*10) % 13] += dp[i][j]%(10**9+7)

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


print(dp[le][5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
S = [int(x) if x != '?' else - 1 for x in input()]
le=len(S)

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

i=0
for k in reversed(S):
    if k==-1:
        for s in range(10):
            for j in range(13):
                dp[i + 1][(s * 10**(i) + j) % 13] += dp[i][j]%(10**9+7)

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


print(dp[le][5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

kj = {}
for k in range(13):
    for j in range(10):
        kj[(k, j)] = (k * 10 + j) % 13

dp[0][0] = 1
for i, s in enumerate(S):
    if s == '?':
        for (k, j), v in kj.items():
            dp[i+1][v] += dp[i][k]
    else:
        s_int = int(s)
        for k in range(13):
            dp[i+1][kj[(k, s_int)]] += dp[i][k]
        
    for j in range(13):
        dp[i+1][j] %= 10**9 + 7

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

Submission status: Time Limit Exceeded

Solution code:
S=list(input())

dp=[(i,0) for i in range(13)]
dp=dict(dp)
dp[0]=1

i=0
for k in reversed(S):
    newdp=dict([(i,0) for i in range(13)])
    if k=='?':
        for s in range(10):
            p=(s * 10**(i))%13
            for j in range(13):               
                newdp[(p + j) % 13] += dp[j]%(10**9+7)
    else:
        k=int(k)
        p=(k * 10**(i))%13
        for j in range(13):
            newdp[(p + j) % 13] += dp[j]%(10**9+7)
    dp=newdp
    i += 1


print(dp[5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
S=list(input())

dp=[(i,0) for i in range(13)]
dp=dict(dp)
dp[0]=1

i=0
for k in reversed(S):
    dpcopy=dp.copy()
    dp=dict([(i,0) for i in range(13)])
    if k=='?':
        for s in range(10):
            p=(s * 10**(i))%13
            for j in range(13):               
                dp[(p + j) % 13] += dpcopy[j]%(10**9+7)
    else:
        k=int(k)
        p=(k * 10**(i))%13
        for j in range(13):
            dp[(p + j) % 13] += dpcopy[j]%(10**9+7)
    i += 1


print(dp[5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
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(10):
            for k in range(13):
                dp[i+1][(k * 10 + j) % 13] += dp[i][k]
    else:
        s_int = int(s)
        for k in range(13):
            dp[i+1][(k * 10 + s_int) % 13] += dp[i][k]
        
    for j in range(13):
        dp[i+1][j] %= 10**9 + 7

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

Submission status: Time Limit Exceeded

Solution code:

#readed editional
MOD = int(1e9)+7
#print(MOD)
S = [int(x) if x != '?' else - 1 for x in input()]

n = len(S)

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

dp[0][0] = 1
#print(dp)

for i in range(n):
    c = S[i]
    if c == -1:
        for j in range(10):
            for ki in range(13):
                dp[i + 1][(ki * 10 + j) % 13] += dp[i][ki]
    else:
        for ki in range(13):
            dp[i + 1][(ki * 10 + c) % 13] += dp[i][ki]        
    for j in range(13):
        dp[i+1][j] %= MOD

#print(S)
#print(dp)
print(dp[len(dp)-1][5])

Submission status: Time Limit Exceeded

Solution code:

#readed editional
MOD = int(1e9)+7
#print(MOD)
S = [int(x) if x != '?' else - 1 for x in input()]

n = len(S)

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

dp[0][0] = 1
#print(dp)

for i in range(n):
    c = S[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

#print(S)
#print(dp)
print(dp[len(dp)-1][5])

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
S = input()

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

dp[0][0] = 1
for i, s in enumerate(S):
    for j in range(10):
        if s != '?' and int(s) != j:
            continue
        for k in range(13):
            dp[i+1][(k * 10 + j) % 13] += dp[i][k]
        
    for j in range(13):
        dp[i+1][j] %= 10**9 + 7

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

Submission status: Time Limit Exceeded

Solution code:
from pprint import pprint
S = input()
N = len(S)

def main():
    dp = [[0 for _ in range(13)] for _ in range(N + 1)]

    dp[0][0] = 1

    # pprint(dp)

    for i in range(N):
        if S[i] == '?':
            c = -1
        else:
            c = int(S[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] %= 1000000007

    # pprint(dp)

    print(dp[N][5])

main()

Submission status: Time Limit Exceeded

Solution code:
S=list(input())

dp=[(i,0) for i in range(13)]
dp=dict(dp)
dp[0]=1

i=0
for k in reversed(S):
    dpcopy=dp.copy()
    dp=dict([(i,0) for i in range(13)])
    if k=='?':
        for s in range(10):
            p=(s * 10**(i))%13
            for j in range(13):               
                dp[(p + j) % 13] += dpcopy[j]%(10**9+7)
    else:
        k=int(k)
        p=(k * 10**(i))%13
        for j in range(13):
            dp[(p + j) % 13] += dpcopy[j]%(10**9+7)
    i += 1


print(dp[5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
S=list(input())

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

i=0
for k in reversed(S):
    dpcopy=dp.copy()
    dp=[0 for i in range(13)]
    if k=='?':
        for s in range(10):
            p=(s * 10**(i))%13
            for j in range(13):               
                dp[(p + j) % 13] += dpcopy[j]%(10**9+7)
    else:
        k=int(k)
        p=(k * 10**(i))%13
        for j in range(13):
            dp[(p + j) % 13] += dpcopy[j]%(10**9+7)
    i += 1


print(dp[5]%(10**9+7))

Submission status: Time Limit Exceeded

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

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

i=0
for k in reversed(S):
    dpcopy=dp.copy()
    dp=[0 for i in range(13)]
    if k=='?':
        for s in range(10):
            for j in range(13):               
                dp[(s * 10**(i) + j) % 13] += dpcopy[j]%(10**9+7)
    else:
        k=int(k)
        for j in range(13):
            dp[(k * 10**(i) + j) % 13] += dpcopy[j]%(10**9+7)
    i += 1


print(dp[5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
S=list(input())
le=len(S)
dp=[[0 for i in range(13)] for j in range(le+1)]
dp[0][0] = 1

def xin(A,n):
    li=[0]*13
    for i in range(13):
        li[(i+n)%13] = A[i]%(10**9+7)
    return li


i=0
for k in reversed(S):
    if k=='?':
        for s in range(10):
            for j in range(13):
                dp[i + 1][(s * 10**(i) + j) % 13] += dp[i][j]%(10**9+7)

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


print(dp[le][5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
S=list(input())
le=len(S)
dp=[[0 for i in range(13)] for j in range(le+1)]
dp[0][0] = 1

def xin(A,n):
    li=[0]*13
    for i in range(13):
        li[(i+n)%13] = A[i]%(10**9+7)
    return li


i=0
for k in reversed(S):
    if k=='?':
        for s in range(10):
            for j in range(13):
                dp[i + 1][(s * 10**(i) + j) % 13] += dp[i][j]%(10**9+7)

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


print(dp[le][5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N=input()

lists = []
temp=np.asarray([i for i in range(10)])

MOD=10**9+7

dic={0:1}

for i in N:
    new_dic={}
    hoge=list(dic.items())
    if i == "?":
        for amari,count in hoge:
            amari*=10
            a=(temp+amari)%13
            for pa in a:
                if pa in new_dic:
                    new_dic[pa]+=count
                else:
                    new_dic[pa]=count
    else:
        num=int(i)
        for amari,count in hoge:
            a = (amari*10 + num)%13
            if a in new_dic:
                new_dic[a]+=count
            else:
                new_dic[a]=count
    for key in new_dic:
        new_dic[key] %= MOD
    dic = new_dic

try:
    print(dic[5])
except:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N=input()

lists = []
temp=np.asarray([i for i in range(10)])

dic={0:1}

for i in N:
    new_dic={}
    hoge=list(dic.items())
    if i == "?":
        for amari,count in hoge:
            amari*=10
            a=(temp+amari)%13
            for pa in a:
                if pa in new_dic:
                    new_dic[pa]+=count
                else:
                    new_dic[pa]=count
    else:
        num=int(i)
        for amari,count in hoge:
            a = (amari*10 + num)%13
            if a in new_dic:
                new_dic[a]+=count
            else:
                new_dic[a]=count
    dic = new_dic

try:
    print(dic[5]%(10**9 + 7))
except:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N=input()

lists = []
temp=np.asarray([i for i in range(10)])

dic={0:1}

for i in N:
    new_dic={}
    hoge=list(dic.items())
    if i == "?":
        for amari,count in hoge:
            amari*=10
            for num in temp:
                a = (amari + num) % 13
                if a in new_dic:
                    new_dic[a]+=count
                else:
                    new_dic[a]=count
    else:
        num=int(i)
        for amari,count in hoge:
            a = (amari*10 + num)%13
            if a in new_dic:
                new_dic[a]+=count
            else:
                new_dic[a]=count
    dic = new_dic

try:
    print(dic[5]%(10**9 + 7))
except:
    print(0)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N=input()

lists = []
temp=[i for i in range(10)]

dic={0:1}

for i in N:
    new_dic={}
    hoge=list(dic.items())
    if i == "?":
        for amari,count in hoge:
            amari*=10
            for num in temp:
                a = (amari + num) % 13
                if a in new_dic:
                    new_dic[a]+=count
                else:
                    new_dic[a]=count
    else:
        num=int(i)
        for amari,count in hoge:
            a = (amari*10 + num)%13
            if a in new_dic:
                new_dic[a]+=count
            else:
                new_dic[a]=count
    dic = new_dic

try:
    print(dic[5]%(10**9 + 7))
except:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
S = input()
dp = [[0 for _ in range(13)] for _ in range(len(S))]
if S[0] == "?":
  for i in range(10):
    dp[0][i] = 1
else:
  dp[0][int(S[0])] = 1
#print(dp)
for i in range(len(S) - 1):
  if S[i + 1] == "?":
    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[i + 1])) % 13] += dp[i][j] 
#print(dp)
print(dp[len(S) - 1][5] % (10 ** 9 + 7))