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:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  s=S()
  n=len(s)

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

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

  return dp[n][5]

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys,math,copy
import numpy as np
input = sys.stdin.readline
S = [int(x) if x != '?' else -1 for x in input().strip()]
N = len(S)

dp_ = np.zeros((13), dtype=int)
dp_[0] = 1
mod = 1
for i, s in enumerate(S[::-1], start=1):
    dp = np.zeros((13), dtype=int)
    if s == -1:
        for d in range(10):
            m = (d * mod) % 13
            for pm in range(13):
                dp[(pm+m)%13] = (dp[(pm+m)%13] + dp_[pm]) % (10 ** 9 + 7)

    else:
        m = (s * mod) % 13
        for pm in range(13):
            dp[(pm+m)%13] = (dp[(pm+m)%13] + dp_[pm]) % (10 ** 9 + 7)
    dp_ = dp
    mod = (mod * 10) % 13
print(dp_[5] % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import sys,math,copy
input = sys.stdin.readline
S = [int(x) if x != '?' else -1 for x in input().strip()]
N = len(S)

dp = [[0] * 13 for _ in range(2)]
dp[0][0] = 1
mod = 1
for i, s in enumerate(S[::-1], start=1):
    n = i % 2
    if s == -1:
        for d in range(10):
            m = (d * mod) % 13
            for pm in range(13):
                dp[n][(pm+m)%13] += dp[n-1][pm]

    else:
        m = (s * mod) % 13
        for pm in range(13):
            dp[n][(pm+m)%13] += dp[n-1][pm]
    dp[n-1] = [0] * 13
    mod = (mod * 10) % 13
print(dp[N%2][5] % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import sys,math,copy
input = sys.stdin.readline
S = input().strip()
N = len(S)

dp = [[0] * 13 for _ in range(2)]
dp[0][0] = 1
mod = 1
for i, s in enumerate(S[::-1], start=1):
    n = i % 2
    if s == '?':
        for d in range(10):
            m = (d * mod) % 13
            for pm in range(13):
                dp[n][(pm+m)%13] += dp[n-1][pm]

    else:
        m = (int(s) * mod) % 13
        for pm in range(13):
            dp[n][(pm+m)%13] += dp[n-1][pm]
    dp[n-1] = [0] * 13
    mod = (mod * 10) % 13
print(dp[N%2][5] % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import sys,math,copy
input = sys.stdin.readline
S = input().strip()
N = len(S)

dp = [[0] * 13 for _ in range(N+1)]
dp[0] = [1] * 13
mod = 1
if S[-1] == '?':
    for d in range(10):
        dp[1][(d * mod) % 13] = 1
else:
    dp[1][(int(S[-1]) * mod) % 13] = 1

S = S[0:N-1]
for n, s in enumerate(S[::-1], start=2):
    mod = (mod * 10) % 13
    if s == '?':
        for d in range(10):
            m = (d * mod) % 13
            for pm in range(13):
                dp[n][(pm+m)%13] += dp[n-1][pm]
    else:
        m = (int(s) * mod) % 13
        for pm in range(13):
            dp[n][(pm+m)%13] += dp[n-1][pm]

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

Submission status: Time Limit Exceeded

Solution code:
import sys,math,copy
input = sys.stdin.readline
S = input().strip()
N = len(S)

dp = [[0] * 13 for _ in range(N+1)]
dp[0] = [1] * 13
if S[0] == '?':
    for d in range(10):
        dp[1][(d * 10 ** (N-1)) % 13] = 1
else:
    dp[1][(int(S[0]) * 10 ** (N-1)) % 13] = 1

for n, s in enumerate(S[1:], start=2):
    if s == '?':
        for d in range(10):
            m = (d * 10 ** (N-n)) % 13
            for pm in range(13):
                dp[n][(pm+m)%13] += dp[n-1][pm]
    else:
        m = (int(s) * 10 ** (N-n)) % 13
        for pm in range(13):
            dp[n][(pm+m)%13] += dp[n-1][pm]

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

s = input()
n = len(s)

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

for i in range(n):
    if s[i] != '?':
        for j in range(13):
            a = s[i]
            a = int(a)
            keta = (j*10 + a) % 13
            dp[i+1][keta] += dp[i][j]
            dp[i+1][keta] % MOD
    else:
        for j in range(13):
            for k in range(10):
                keta = (j*10 + k) % 13
                dp[i+1][keta] += dp[i][j]
                dp[i+1][keta] % MOD
                
print(dp[n][5] % MOD)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

for i in range(1,len_s):

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

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

Submission status: Time Limit Exceeded

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

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

for i in range(1,len_s):

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

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

Submission status: Time Limit Exceeded

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

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

for i in range(1,len_s):

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

MOD = 10**9+7

def main():
    S = input()
    n = len(S)
    dp = [[0]* 13 for _ in range(10**5+100)]
    dp[0][0] = 1
    for i in range(n):
        c = -1 if S[i] == '?' else ord(S[i]) - ord('0')
        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
    res = dp[n][5]
    print(res)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
s=input()
dp1=[1]+[0]*12
for i in range(len(s)):
    dp2=[0]*13
    if s[i]!='?':
        p=int(s[i])
        for j in range(13):
            dp2[(j*10+p)%13]+=dp1[j]
    else:
        for p in range(10):
            for j in range(13):
                dp2[(j*10+p)%13]+=dp1[j]
    dp1=[dp2[j]%mod for j in range(13)]
print(dp1[5])

Submission status: Time Limit Exceeded

Solution code:
s=input()
#print(s)
n=len(s)
mod=10**9+7
dp=[[0 for _ in range(13)] for _ in range(n)]
for i,x in enumerate(s):
#    print(i,x)
    if i==0:
 #       print( i,end=' i entered\n')
        if x=='?':
            for j in range(10):
                dp[0][j]=1
        else:
  #          print(x,end=' x\n')
            num=int(x)
   #         print(num,end=' num\n')
            dp[0][num]=1
    else:
        if x=='?':
            for j in range(10):
                for jj in range(13):
                    if dp[i-1][jj]>0:
                        dp[i][(10*jj+j)%13]=(dp[i][(10*jj+j)%13]+dp[i-1][jj])
        else:
            num=int(x)
            for j in range(13):
                if dp[i-1][j]>0:
                    dp[i][(10*j+num)%13]=(dp[i][(10*j+num)%13]+dp[i-1][j])
print(dp[-1][5]%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import copy
S=list(input())
mod=10**9+7
dict={}
tdict={}

for i in range(13):
    dict[i]=0
    tdict[i]=0
s=S.pop()
if s=="?":
    for k in range(10):
        dict[k]=1
else:
    dict[int(s)]=1
i=1
while S:
    s=S.pop()
    tmpdict=copy.copy(tdict)
    if s!="?":
        m=(int(s)*(10**i))%13

        for l in range(13):
            tmpdict[(l+m)%13]=(tmpdict[(l+m)%13]+dict[l])%mod
        dict=copy.copy(tmpdict)
    else:
        for k in range(10):
            m=(k*(10**i))%13
            for l in range(13):
                tmpdict[(l+m)%13]=(tmpdict[(l+m)%13]+dict[l])%mod
        dict=copy.copy(tmpdict)
    i+=1
print(dict[5])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
mod=10**9+7
dp=[[0 for _ in range(13)] for _ in range(n)]
for i,x in enumerate(s):
    if i==0:
        if x=='?':
            for j in range(10):
                dp[0][j]=1
        else:
            num=ord(x)-ord('0')
            dp[0][num]=1
    else:
        if x=='?':
            for j in range(10):
                for jj in range(13):
                    if dp[i-1][jj]>0:
                        dp[i][(10*jj+j)%13]=(dp[i][(10*jj+j)%13]+dp[i-1][jj])%mod
        else:
            num=ord(x)-ord('0')
            for j in range(13):
                if dp[i-1][j]>0:
                    dp[i][(10*j+num)%13]=(dp[i][(10*j+num)%13]+dp[i-1][j])%mod
print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
mod=10**9+7
dp=[[0 for _ in range(13)] for _ in range(n)]
for i,x in enumerate(s):
    if i==0:
        if x=='?':
            for j in range(10):
                dp[0][j]=1
        else:
            num=ord(x)-ord('0')
            dp[0][num]=1
    else:
        if x=='?':
            for j in range(10):
                for jj in range(13):
                    if dp[i-1][jj]>0:
                        dp[i][(10*jj+j)%13]+=dp[i-1][jj]
        else:
            num=ord(x)-ord('0')
            for j in range(13):
                if dp[i-1][j]>0:
                    dp[i][(10*j+num)%13]+=dp[i-1][j]
print(dp[-1][5]%mod)

Submission status: Time Limit Exceeded

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

dp = [[0] * 13 for _ in range(2)]
tmp = 0
for si in s:
    if(si != '?'):
        tmp = (tmp*10 + int(si)) % 13
    else:
        tmp = tmp*10 % 13

dp[0][tmp] = 1
exp10 = 1
pointer = 0
for i,si in enumerate(s[::-1]):

    if(si!='?'):
        exp10 = exp10 * 10 % 13
        continue

    pointer = 1 - pointer
    for j in range(13):
        dp[pointer][j] = 0

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

    for j in range(13):
        dp[pointer][j] %= mod

    exp10 = exp10 * 10 % 13

print(dp[pointer][5])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    mod = 10**9 + 7

    s = input().rstrip()
    n = len(s)
    dp = [[0]*13 for _ in range(n)]

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

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    mod = 10**9 + 7

    s = input().rstrip()
    n = len(s)
    dp = [[0]*13 for _ in range(n)]

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

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
s = s[::-1]

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

for ind, i in enumerate(s):
    m = 10**ind%13
    tmp = [0]*13
    for j in range(10):
        if i!='?' and int(i)!=j:
            continue
        for k in range(13):
            tmp[k] += dp[(k-j*m%13)%13]
    dp = tmp
print(dp[5]%(10**9+7))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s = input()

frommap = []
for d in range(10):
    frommap.append([0] * 13)
    for m in range(13):
        m2 = (m * 10 + d) % 13
        frommap[d][m2] = m

dp = [1] + [0] * 12
for c in s:
    if c == '?':
        dp = [sum(dp[frommap[d][m]] for d in range(10)) % 1000000007 for m in range(13)]
    else:
        f = frommap[int(c)]
        dp = [dp[f[m]] for m in range(13)]

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
mod=10**9+7
dp=[[0]*13 for i in range(n+1)] # dp[i][j]:i番目までで j mod 13.
dp[0][0]=1
for i in range(1,n+1):
  for j in range(13):
    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=input()
M=13
MOD=10**9+7
dp=[[0]*M for i in range(len(S))]
tmp=[0]*M
tmp[0]=1
for i in range(len(S)):
  s=S[i]
  if s=='?':
    for s in range(10):
      for j,d in enumerate(tmp):
        dp[i][(j+s)%M]+=d
        #dp[i+1][(j+s)%M]+=d
  else:
    s=int(s)
    for j,d in enumerate(tmp):
      dp[i][(j+s)%M]=d
  for j,d in enumerate(dp[i]):
    tmp[(10*j)%M]=d%MOD
print(dp[-1][5]%MOD)

Submission status: Time Limit Exceeded

Solution code:
S=input()
M=13
MOD=10**9+7
dp=[[0]*M for i in range(2)]
dp[1][0]=1
for i in range(len(S)):
  dp[0]=[0]*13
  s=S[i]
  if s=='?':
    for s in range(10):
      for j,d in enumerate(dp[1]):
        dp[0][(j+s)%M]+=d
        #dp[0][(j+s)%M]%=MOD
  else:
    s=int(s)
    for j,d in enumerate(dp[1]):
      dp[0][(j+s)%M]=d
  for j,d in enumerate(dp[0]):
    dp[1][(10*j)%M]=d%MOD
print(dp[0][5]%MOD)

Submission status: Time Limit Exceeded

Solution code:
S=input()
M=13
MOD=10**9+7
dp=[[0]*M for i in range(2)]
dp[1][0]=1
for i in range(len(S)):
  dp[0]=[0]*13
  s=S[i]
  if s=='?':
    for s in range(10):
      for j,d in enumerate(dp[1]):
        dp[0][(j+s)%M]+=d
        #dp[0][(j+s)%M]%=MOD
  else:
    s=int(s)
    for j,d in enumerate(dp[1]):
      dp[0][(j+s)%M]=d
  for j,d in enumerate(dp[0]):
    dp[1][(10*j)%M]=d
print(dp[0][5]%MOD)

Submission status: Time Limit Exceeded

Solution code:
S=input()
x=0
M=13
MOD=10**9+7
dp=[[0]*M for i in range(2)]
dp[1][0]=1
for i in range(len(S)):
  dp[0]=[0]*13
  s=S[i]
  if s=='?':
    for s in range(10):
      for j,d in enumerate(dp[1]):
        dp[0][(j+s)%M]+=d
        dp[0][(j+s)%M]%=MOD
  else:
    s=int(s)
    for j,d in enumerate(dp[1]):
      dp[0][(j+s)%M]=d
  for j,d in enumerate(dp[0]):
    dp[1][(10*j)%M]=d
print(dp[0][5]%MOD)

Submission status: Time Limit Exceeded

Solution code:
S=input()
x=0
M=13
MOD=10**9+7
dp=[[0]*M for i in range(2)]
dp[0][0]=1
p=0
for i in range(len(S)):
  s=S[i]
  if s=='?':
    for s in range(10):
      for j,d in enumerate(dp[p%2]):
        dp[(p+1)%2][(10*j+s)%M]+=d
        dp[(p+1)%2][(10*j+s)%M]%=MOD
  else:
    s=int(s)
    for j,d in enumerate(dp[p%2]):
      dp[(p+1)%2][(10*j+s)%M]=d
  dp[p%2]=[0]*13
  p+=1
  p%=2
print(dp[p%2][5]%MOD)

Submission status: Time Limit Exceeded

Solution code:
S=input()
M=13
MOD=10**9+7
dp=[[0]*M for i in range(len(S)+1)]
dp[0][0]=1
for i in range(len(S)):
  s=S[i]
  if s=='?':
    for s in range(10):
      for j,d in enumerate(dp[i]):
        dp[i+1][(10*j+s)%M]+=d
        dp[i+1][(10*j+s)%M]%=MOD
  else:
    s=int(s)
    for j,d in enumerate(dp[i]):
      dp[i+1][(10*j+s)%M]=d
print(dp[-1][5]%MOD)

Submission status: Time Limit Exceeded

Solution code:
S=input()
M=13
MOD=10**9+7
dp=[[0]*M for i in range(len(S)+1)]
dp[0][0]=1
for i in range(len(S)):
  s=S[i]
  if s=='?':
    for s in range(10):
      for j,d in enumerate(dp[i]):
        dp[i+1][(10*j+s)%M]+=d
  else:
    s=int(s)
    for j,d in enumerate(dp[i]):
      dp[i+1][(10*j+s)%M]=d
print(dp[-1][5]%MOD)

Submission status: Time Limit Exceeded

Solution code:
S=input()
x=0
M=13
MOD=10**9+7
dp=[[0]*M for i in range(2)]
dp[0][0]=1
p=0
for i in range(len(S)):
  s=S[i]
  if s=='?':
    for s in range(10):
      for j,d in enumerate(dp[p%2]):
        dp[(p+1)%2][(10*j+s)%M]+=d
  else:
    s=int(s)
    for j,d in enumerate(dp[p%2]):
      dp[(p+1)%2][(10*j+s)%M]=d
  dp[p%2]=[0]*13
  p+=1
  p%=2
print(dp[p%2][5]%MOD)

Submission status: Time Limit Exceeded

Solution code:
S = input().strip()
mod = 10**9 + 7
d = [i*10%13 for i in range(13)]
dp = [[0]*13 for _ in range(len(S)+1)]
dp[0][0] = 1
for i, c in enumerate(S, 1):
    if c != '?':
        c = int(c)
        for j in range(13):
            dp[i][(d[j] + c) % 13] = dp[i-1][j]
    else:
        for c in range(10):
            for j in range(13):
                k = (d[j] + c) % 13
                dp[i][k] += dp[i-1][j]
        for j in range(13):
            dp[i][j] %= mod
print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
S = input().strip()
mod = 10**9 + 7
d = {i:i*10%13 for i in range(13)}
dp = [[0]*13 for _ in range(len(S)+1)]
dp[0][0] = 1
for i, c in enumerate(S, 1):
    if c != '?':
        c = int(c)
        for j in range(13):
            dp[i][(d[j] + c) % 13] = dp[i-1][j] % mod
    else:
        for c in range(10):
            for j in range(13):
                k = (d[j] + c) % 13
                dp[i][k] = (dp[i][k] + dp[i-1][j]) % mod
print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
#python3
from copy import copy
MOD = int(1e9)+7

def main():
    s = input()
    n = len(s)
    dp = [0 for _ in range(13)]
    dp[0] = 1 
    mul = 1
    for i in reversed(range(n)):
        nextDP = [0 for _ in range(13)]
        if s[i] == '?':
            for j in range(13):
                for k in range(10):
                    nextDP[(k*mul + j)%13] += dp[j]
                    nextDP[(k*mul + j)%13] %= MOD
        else:
            x = ord(s[i]) - ord('0')
            for j in range(13):
                nextDP[(x*mul + j)%13] += dp[j]
                nextDP[(x*mul + j)%13] %= MOD
        dp = copy(nextDP)
        mul *= 10
        mul %= 13
    print(dp[5])
main()

Submission status: Time Limit Exceeded

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

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

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

MOD = 10 ** 9 + 7


dp = [np.zeros(13, dtype=np.int64) for _ in range(LS + 1)]
dp[0][0] = 1

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

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

            if md == 0:
                dp[i + 1] += dp[i]
            else:
                dp[i + 1][md:] += dp[i][:-md]
                dp[i + 1][:md] += dp[i][-md:]
            dp[i + 1] %= MOD

#print("i == LS")
#print(dp[LS])
print(dp[LS][5])

Submission status: Time Limit Exceeded

Solution code:
#python3
from copy import copy
MOD = int(1e9)+7

def main():
    s = input()
    n = len(s)
    dp = [0 for _ in range(13)]
    dp[0] = 1 
    mul = 1
    for i in reversed(range(n)):
        nextDP = [0 for _ in range(13)]
        if s[i] == '?':
            for j in range(13):
                for k in range(10):
                    nextDP[(k*mul + j)%13] += dp[j]
                    nextDP[(k*mul + j)%13] %= MOD
        else:
            x = ord(s[i]) - ord('0')
            for j in range(13):
                nextDP[(x*mul + j)%13] += dp[j]
                nextDP[(x*mul + j)%13] %= MOD
        dp = copy(nextDP)
        mul *= 10
    print(dp[5])
main()

Submission status: Time Limit Exceeded

Solution code:
#python3
from copy import copy
MOD = int(1e9)+7

def main():
    s = input()
    n = len(s)
    dp = [0 for _ in range(13)]
    dp[0] = 1 
    mul = 1
    for i in reversed(range(n)):
        nextDP = [0 for _ in range(13)]
        if s[i] == '?':
            for j in range(13):
                for k in range(10):
                    nextDP[(k*mul + j)%13] += dp[j]
                    nextDP[(k*mul + j)%13] %= MOD
        else:
            x = ord(s[i]) - ord('0')
            for j in range(13):
                nextDP[(x*mul + j)%13] += dp[j]
                nextDP[(x*mul + j)%13] %= MOD
        dp = copy(nextDP)
        mul *= 10
    print(dp[5])
main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
dp = [1] + [0] * 12
for c in s:
    newdp = [0] * 13
    for d in range(10) if c == '?' else [int(c)]:
        for m in range(13):
            m2 = (m * 10 + d) % 13
            newdp[m2] = (newdp[m2] + dp[m]) % 1000000007
    dp = newdp
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

def main():
    s = input().strip()
    MOD = int(1e9) + 7

    dp = np.zeros(13, dtype=int)
    dp[0] = 1
    tmp = 1
    for c in s[::-1]:
        next_ = np.zeros(13, dtype=int)
        if c == "?":
            # 0~9までを考える
            for i in range(10):
                next_ += np.roll(dp, (i*tmp)%13)
        else:
            c = int(c)
            next_ = np.roll(dp, (c*tmp)%13)
        # print(next_)
        dp = next_ % MOD
        tmp *= 10
        tmp %= 13

    print(dp[5])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
dp = [0] * (13 * (len(S) + 1))
ij = lambda i,j: i*13 + j
dp[ij(0,0)] = 1
pos = 1

MOD = 10**9 + 7

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

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

Submission status: Time Limit Exceeded

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

# dp[i][j] = 上からi桁目まで見た時のjと合同な数の個数
dp =[[0]*13 for _ in range(l+1)]
dp[0][0] = 1
for i in range(l):
    if s[i] == '?':
        for j in range(13):
            for k in range(10):
                dp[i+1][(j*10+k)%13] += dp[i][j]
                dp[i+1][(j*10+k)%13] %= mod
    else:
        for j in range(13):
            dp[i+1][(j*10+int(s[i]))%13] += dp[i][j]
print(dp[l][5]%mod)

Submission status: Time Limit Exceeded

Solution code:
INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろ(小さい位)からi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10

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