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:
#!/usr/bin/env python

import sys

s= sys.stdin.readline().strip()
n= len(s)
#
MOD=10**9+7
#
base = 1
dp= [ [0]*13 for _ in range(n+1) ]
dp[0][0] = 1
for i,c in enumerate(reversed(s)):
    prev= dp[i]
    now = dp[i+1]
    #
    if c=="?":
        for b in [ base*i for i in range(10) ]:
            for m,num in enumerate(prev):
                if num==0: continue
                idx= (m+b)%13
                now[idx]= now[idx]+num
        #
        for i in range(13): now[i] %= MOD
    else:
        b= base*int(c)
        for m in range(13):
            idx= (m+b)%13
            now[idx]= prev[m]
    #
    base = base*10
#
print(dp[n][5])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2**31-1)
input = sys.stdin.readline
write = sys.stdout.write
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = True



MOD = 10**9 + 7
class ModInt:

    def __init__(self, x):
        self.x = x.x if isinstance(x, ModInt) else x % MOD

    __str__ = lambda self:str(self.x)
    __repr__ = __str__
    __int__ = lambda self: self.x
    __index__ = __int__

    __add__ = lambda self, other: ModInt(self.x + ModInt(other).x)
    __sub__ = lambda self, other: ModInt(self.x - ModInt(other).x)
    __mul__ = lambda self, other: ModInt(self.x * ModInt(other).x)
    __pow__ = lambda self, other: ModInt(pow(self.x, ModInt(other).x, MOD))
    __mod__ = lambda self, other: ModInt(self.x % ModInt(other).x)
    __truediv__ = lambda self, other: ModInt(self.x * pow(ModInt(other).x, MOD - 2, MOD))
    __floordiv__ = lambda self, other: ModInt(self.x // ModInt(other).x)
    __radd__ = lambda self, other: ModInt(other + self.x)
    __rsub__ = lambda self, other: ModInt(other - self.x)
    __rpow__ = lambda self, other: ModInt(pow(other, self.x, MOD))
    __rmod__ = lambda self, other: ModInt(other % self.x)
    __rmul__ = lambda self, other: ModInt(other * self.x)
    __rtruediv__ = lambda self, other: ModInt(other * pow(self.x, MOD - 2, MOD))
    __rfloordiv__ = lambda self, other: ModInt(other // self.x)

    __lt__ = lambda self, other: self.x < ModInt(other).x
    __gt__ = lambda self, other: self.x > ModInt(other).x
    __le__ = lambda self, other: self.x <= ModInt(other).x
    __ge__ = lambda self, other: self.x >= ModInt(other).x
    __eq__ = lambda self, other: self.x == ModInt(other).x
    __ne__ = lambda self, other: self.x != ModInt(other).x


def main():
    S = input()
    N = len(S)-1
    dp = [[0] * 13  for _   in range(N)]
    dp[0] = [0 for _ in range(13)]
    
    if S[0] == '?':
        for i in range(10):
            dp[0][i] = 1
    else:
        dp[0][int(S[0])] = 1

    for i in range(1,N):
        if S[i] == '?':
            R = range(10)
        else:
            R = [int(S[i])]

        for j in range(13):
            for k in R:
                dp[i][(j * 10 + k) % 13 ] = (dp[i][(j * 10 + k) % 13 ] + dp[i-1][j]) 
        # for j in range(13):
        #     dp[i][j] %= MOD
    
    print(dp[len(S)-2][5] % MOD)









    pass
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

# やりやすさのため、小さい桁からいけるように逆順にしておく
S=input()[::-1]
N=len(S)

# dp[i][j] := 下からi桁を考えた時，13で割ったあまりがjであるものの数
dp=list2d(N+1, 13, 0)
dp[0][0]=1
for i in range(N):
    for j in range(13):
        # ?だったら0~9を全て遷移させる
        if S[i]=='?':
            for k in range(10):
                # 桁を合わせる
                nxt=k*10**i
                dp[i+1][(j+nxt)%13]+=dp[i][j]
                dp[i+1][(j+nxt)%13]%=MOD      
        else:
            # 決まっていたらその数字のみ遷移させる
            nxt=int(S[i])*10**i
            dp[i+1][(j+nxt)%13]+=dp[i][j]
            dp[i+1][(j+nxt)%13]%=MOD
# 最終的にN桁終わって余り5の数が答え
print(dp[N][5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
dp = [0 for _ in range(13)]
dp[0] = 1
c = 1000000007
m = 1
r13 = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
r10 = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
for i in range(len(s) - 1, -1, -1):
    ndp = [0 for _ in r13]
    if s[i] == "?":
        for j in r10:
            jm = j * m
            for k in r13:
                index = (jm + k) % 13
                ndp[index] = (ndp[index] + dp[k]) % c
    else:
        jm = int(s[i]) * m
        for k in r13:
            index = (jm + k) % 13
            ndp[index] = (ndp[index] + dp[k]) % c
    dp = ndp[:]
    m = m * 10 % 13
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
""" dpはi桁,あまりj
[[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
"""
S = str(input())
S = S[::-1]
n = len(S)

dp = [[0]*(13) for _ in range(n+1)]
dp[0][0]=1 #0を割ったあまりは0

q = 1 # はじめの1桁のときはあまりは1

# i桁目のあまりが何通りあるか
for i in range(1,n+1): # 「1-n」桁まで
  s = S[i-1]
  for j in range(13): # 13で割ったあまり
    
    if s == '?': # ?の場合は0-9を計算する
      for k in range(10):
        dp[i][(j+k*q)%13] += dp[i-1][j] # i-1桁目からi桁目 +=を忘れずに！
    else:
      k = int(s)
      dp[i][(j+k*q)%13] += dp[i-1][j] # i-1桁目からi桁目
      
  q = (10*q)%13 # 「10^iをqで割ったあまり」

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
arr = [0] * len(S)
ans = 0
tmp = 0
max = int(S.replace('?', '9'))
min = int(S.replace('?', '0'))
for i in range(len(S)):
    if S[i] == '?':
        arr[i] = 10
    else:
        arr[i] = S[i]

# print(max)
# print(min)
# print(arr)
tmp = min

while(1):
    if tmp % 13 == 5:
        # print('ok')
        break
    else:
        tmp += 1

# print(tmp)
dd = False
for i in range(tmp,max+1,13):
    st = str(i)
    l = 0
    for k in range(len(S)-len(st),len(S)):
        if (arr[k] != 10) and (arr[k] != st[l]):
            dd = True
            break
        l += 1
    if dd == False:
        ans += 1
    else:
        dd=False
        # print('ok')
        # print(i)

# if tmp % 13 == 5:
#     ans += 1
# print(tmp)
print(ans % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
S = list(input())
u = 10**9+7
d = len(S)
dp = np.zeros(13, dtype=np.int64)
dp[0] = 1
m = 1

for i in range(d-1,-1,-1):
    tmp = np.zeros(13, dtype=np.int64)
    a = S[i]
    if a=='?':
        for j in range(10):
            c = j*m
            for k in range(13):
                n = (c+k)%13
                tmp[n] += dp[k]
                tmp[n] %= u
    else:
        c = int(a)*m
        for k in range(13):
            n = (c+k)%13
            tmp[n] += dp[k]
            tmp[n] %= u
    m *= 10
    m %= 13
    dp = tmp
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
dp = [[0 for i in range(13)]]
if s[-1] != "?":
    dp[0][int(s[-1]) % 13] += 1
else:
    for k in range(10):
        dp[0][k % 13] += 1
        
d = [1]   
for i in range(1,len(s)):
    dp.append([0]*13)
    d.append(d[i-1]*10 % 13)
    for r in range(13):
        if s[-(i+1)] == "?":
            for k in range(10): 
                dp[i][(k * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)
                
        else:
            dp[i][(int(s[-(i+1)]) * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)

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

Submission status: Time Limit Exceeded

Solution code:
import sys, re
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 LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

S = input()
dp = [[0]*13 for _ 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(10):  # ? が j のとき考える
# 		if c != -1 and c != j:
# 			continue
# 		for k in range(13):
# 			dp[i+1][(k*10+j)%13] = (dp[i+1][(k*10+j)%13] + dp[i][k]) % mod
S = S[::-1]
for i in range(len(S)):
	mul = 10**i
	mul %= 13
	if S[i] == '?':
		for k in range(10):  # ? が k のとき考える
			for j in range(13):
				dp[i+1][(k*mul+j)%13] = (dp[i+1][(k*mul+j)%13] + dp[i][j]) % mod
	else:
		k = int(S[i])
		for j in range(13):
				dp[i+1][(k*mul+j)%13] = (dp[i+1][(k*mul+j)%13] + dp[i][j]) % mod

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
dp = [0 for _ in range(13)]
dp[0] = 1
c = 1000000007
m = 1
r13 = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
r10 = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
for i in range(len(s) - 1, -1, -1):
    ndp = [0 for i in r13]
    if s[i] == "?":
        for j in r10:
            for k in r13:
                index = (j * m + k) % 13
                ndp[index] = (ndp[index] + dp[k]) % c
    else:
        j = int(s[i])
        for k in r13:
            index = (j * m + k) % 13
            ndp[index] = (ndp[index] + dp[k]) % c
    dp = ndp[:]
    m = m * 10 % 13
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
dp = [[0 for i in range(13)] for i in range(len(s))]
if s[-1] != "?":
    dp[0][int(s[-1]) % 13] += 1
else:
    for k in range(10):
        dp[0][k % 13] += 1
        
d = [1]   
for i in range(1,len(s)):
    d.append(d[i-1]*10 % 13)
    for r in range(13):
        if s[-(i+1)] == "?":
            for k in range(10): 
                dp[i][(k * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)
                
        else:
            dp[i][(int(s[-(i+1)]) * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)

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

Submission status: Time Limit Exceeded

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


d=[0 for _ in range(13)]
p=[[i*j%13 for i in range(10)] for j in range(13)]
rev=s[::-1]
num=rev.find("?")
if num==-1:
    b=int(s.replace("?","0"))%13
    if b<=5:
        cal=5-b
    else:
        cal=18-b
    if cal==0:
        print(1)
    else:
        print(0)
else:
    b=0
    tmp=10**num%13
    for i in p[tmp]:
        d[i]+=1
    for i,v in enumerate(rev):
        #print(i+num+1)
        if v=="?" and i>num:
            tmp=10**i%13
            t_d=[0 for _ in range(13)]
            #print("i,tmp:",i+num+1,",",tmp)
            for k in range(0,13):
                for j in range(0,10):
                    t_d[(p[tmp][j]+k)%13]+=d[k]
                #print(t_d)
            #for j in range(13):
                #d[j]=t_d[j]
            d=t_d
            #print(t_d)
        elif v=="?":
            pass
        else:
            b+=int(v)*10**i%13
    b%=13
    if b<=5:
        cal=5-b
    else:
        cal=18-b
    #print(b)
    #print(cal)
    #print(d[7]%mod)
    print(d[cal]%mod)

Submission status: Time Limit Exceeded

Solution code:
s = input()
dp = [0 for i in range(13)]
dp[0] = 1
c = 1000000007
m = 1
for i in range(len(s) - 1, -1, -1):
    ndp = [0 for i in range(13)]
    if s[i] == "?":
        for j in range(10):
            for k in range(13):
                index = (j * m + k) % 13
                ndp[index] = (ndp[index] + dp[k]) % c
    else:
        j = int(s[i])
        for k in range(13):
            index = (j * m + k) % 13
            ndp[index] = (ndp[index] + dp[k]) % c
    dp = ndp[:]
    m = m * 10 % 13
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
dp = [[0 for i in range(13)] for i in range(len(s))]
if s[-1] != "?":
    dp[0][int(s[-1]) % 13] += 1
else:
    for k in range(10):
        dp[0][k % 13] += 1
d = [1]
for i in range(1,len(s)):
    d.append(d[i-1]*10 % 13)
    
for i in range(1,len(s)):
    for r in range(13):
        if s[-(i+1)] == "?":
            for k in range(10): 
                dp[i][(k * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)
                
        else:
            dp[i][(int(s[-(i+1)]) * d[i] + r) % 13] += dp[i-1][r] % (10**9 + 7)

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

Submission status: Time Limit Exceeded

Solution code:
S = input()

mod = 10 ** 9 + 7
N = len(S)
dp = [[0 for _ in range(13)] for _ in range(10 ** 5 + 5)]
dp[0][0] = 1

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

Submission status: Time Limit Exceeded

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

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

for i,c in enumerate(S[1:]):
    for j in range(13):
        if c=='?':
            for k in range(10):
                nj = (j*10 + k) % 13
                dp[i+1][nj] += dp[i][j]
                dp[i+1][nj] %= MOD
        else:
            nj = (j*10 + int(c)) % 13
            dp[i+1][nj] += dp[i][j]
            dp[i+1][nj] %= MOD

print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
def d_digits_parade(S, MOD=10**9 + 7):
    modulo = 13  # 13で割ったあまりを考えている
    # editorialでは2次元配列を考えているが、こうするとメモリを節約できる
    dp = [0] * modulo  # dp[k]: 13で割ったあまりがkの場合の数
    dp[0] = 1  # 初期値を0とすると、これを13で割ったあまりは0

    # Sを下の桁から見ていく
    # ex. 1?2?3: 0 - 3 - ?3 - 2?3 - ...

    mul = 1
    for c in S[::-1]:
        dp_next = [0] * modulo
        if c == '?':
            for k in range(10):  # ?に対し1桁の数字のすべてを試す
                for j in range(modulo):
                    # k * mul: mulの位がk、j: それより下の桁についてのあまり
                    # なので、このような遷移
                    dp_next[(k * mul + j) % modulo] += dp[j]
                    dp_next[(k * mul + j) % modulo] %= MOD
        else:
            k = int(c)
            for j in range(modulo):
                dp_next[(k * mul + j) % modulo] += dp[j]
                dp_next[(k * mul + j) % modulo] %= MOD
        # a*10**d % modulo = (a*(10**d % modulo)) % modulo なので、先に剰余を取る
        mul = (mul * 10) % modulo
        dp = dp_next
    return dp[5]

S = input()
print(d_digits_parade(S))

Submission status: Time Limit Exceeded

Solution code:
s = input()
dp = [[0 for i in range(13)] for i in range(len(s))]
if s[-1] != "?":
    dp[0][int(s[-1]) % 13] += 1
else:
    for k in range(10):
        dp[0][k % 13] += 1
d = [1]
for i in range(1,len(s)):
    d.append(d[i-1]*10 % 13)
    
for i in range(1,len(s)):
    for r in range(13):
        if s[-(i+1)] == "?":
            for k in range(10): 
                dp[i][(k * d[i] + r) % 13] += dp[i-1][r]
                
        else:
            dp[i][(int(s[-(i+1)]) * d[i] + r) % 13] += dp[i-1][r]
    for r in range(13):
        dp[i][r]  %= 10**9 + 7
print(dp[len(s)-1][5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
u = 10**9+7
d = len(S)
dp = [0]*13
dp[0] = 1
m = 1

for i in range(d-1,-1,-1):
    tmp = [0]*13
    a = S[i]
    if a=='?':
        for j in range(10):
            c = j*m
            for k in range(13):
                n = (c+k)%13
                tmp[n] += dp[k]
                tmp[n] %= u
    else:
        c = int(a)*m
        for k in range(13):
            n = (c+k)%13
            tmp[n] += dp[k]
            tmp[n] %= u
    m *= 10
    m %= 13
    dp = tmp
print(dp[5])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from copy import copy
s = input()
dp = [0 for i in range(13)]
m = 1
dp[0] = 1
for i in range(len(s) - 1, -1, -1):
    ndp = [0 for i in range(13)]
    if s[i] == "?":
        for j in range(10):
            for k in range(13):
                ndp[(j * m + k) % 13] += dp[k]
    else:
        j = int(s[i])
        for k in range(13):
            ndp[(j * m + k) % 13] += dp[k]
    dp = copy(ndp)
    m = m * 10 % 13
print(dp[5] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
u = 10**9+7
d = len(S)
dp = [0]*13
dp[0] = 1
m = 1

for i in range(d-1,-1,-1):
    tmp = [0]*13
    a = S[i]
    if a=='?':
        for j in range(10):
            c = j*m
            for k in range(13):
                tmp[(c+k)%13] += dp[k]
                tmp[(c+k)%13] %= u
    else:
        c = int(a)*m
        for k in range(13):
            tmp[(c+k)%13] += dp[k]
            tmp[(c+k)%13] %= u
    m *= 10
    m %= 13
    dp = tmp[:]
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s = input()
p = np.array([0]*13)
p[0] = 1
amari = []

for j in range(10):
  for i in range(13):
    amari.append(((i*10+j)%13,i))

for si in range(len(s)):
  a = np.array([0]*13)
  if s[si] == '?':
    for i in amari:
      a[i[0]] += p[i[1]]
  else:
    c = int(s[si])
    for i in range(13):
      a[(i*10+c)%13] += p[i]
  p = np.mod(a,1000000007)
print(p[5])

Submission status: Time Limit Exceeded

Solution code:
D = 10**9+7
S = input()
mod_table = [[0]*13]
mod_table[0][0] = 1

for i, s in enumerate(S):
    mod_table.append([0]*13)
    if s == "?":
        for num in range(10):
            for d in range(13):
                mod_table[i+1][(d*10+num)%13] += mod_table[i][d]
    else:
        num = int(s)
        for d in range(13):
            mod_table[i+1][(d*10+num)%13] += mod_table[i][d]

print(mod_table[-1][5] % D)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def solve(s):
    MOD = 10 ** 9 + 7
    dp = np.zeros(13, dtype=np.int64)
    idx = [0] * 13
    for i in range(13):
        idx[i * 10 % 13] = i
    window = np.ones(10, dtype=np.int64)
    dp[0] = 1
    for c in s:
        if c == '?':
            tdp = dp[idx]
            ndp = np.concatenate([tdp[4:], tdp])
            dp = np.convolve(ndp, window, mode='valid') % MOD
        else:
            dp = np.roll(dp[idx], int(c))
    return dp[5]


s = input()
print(solve(s))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = input()

N = 13
dp = [0] * N
dp[0]=1
mod =10**9+7
mul =1
#print(dp)
for i in reversed(range(len(S))):
    c = S[i]
    nextDP = [0] * N
    if c == '?':
        for i in range(0,10):
            for j in range(0,N):
                nextDP[(i * mul +j)%N] += dp[j]
                nextDP[(i * mul +j)%N] %= mod

    else:
        i = int(c)
        for j in range(0,N):
            nextDP[(i * mul +j)%N] += dp[j]
            nextDP[(i * mul +j)%N] %= mod

    mul *= 10
    mul %= N
    dp = nextDP

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def solve(s):
    MOD = 10 ** 9 + 7
    dp = np.zeros(13, dtype=np.int64)
    idx = [0] * 13
    for i in range(13):
        idx[i * 10 % 13] = i
    window = [1] * 10
    dp[0] = 1
    for c in s:
        if c == '?':
            tdp = dp[idx]
            ndp = np.concatenate([tdp[4:], tdp])
            dp = np.convolve(ndp, window, mode='valid')
            dp %= MOD
        else:
            i = int(c)
            dp = np.roll(dp[idx], i)
    return dp[5]


s = input()
print(solve(s))

Submission status: Time Limit Exceeded

Solution code:
s = input()
dp = [[0 for i in range(13)] for i in range(len(s))]
if s[-1] != "?":
    dp[0][int(s[-1]) % 13] += 1
else:
    for k in range(10):
        dp[0][k % 13] += 1

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

Submission status: Time Limit Exceeded

Solution code:
s=input()
mod=1000000007

#後ろから解くアルゴリズム
n=13
dp=[0 for _ in range(n)]
dp[0]=1

mul=1
for i in range(len(s)-1, -1, -1):
    nextDP=[0 for _ in range(n)]
    c=s[i]
    if c=='?':
        for k in range(10):
            for j in range(13):
                nextDP[(mul*k+j)%13] += dp[j]
                nextDP[(mul*k+j)%13] %= mod
    else:
        k=int(c)
        for j in range(n):
            nextDP[(mul*k+j)%13] += dp[j]
            nextDP[(mul*k+j)%13] %= mod
    
    mul*=10
    mul%=n
    dp=nextDP.copy()   

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2**31-1)
input = sys.stdin.readline
write = sys.stdout.write
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = True



MOD = 10**9 + 7
class ModInt:

    def __init__(self, x):
        self.x = x.x if isinstance(x, ModInt) else x % MOD

    __str__ = lambda self:str(self.x)
    __repr__ = __str__
    __int__ = lambda self: self.x
    __index__ = __int__

    __add__ = lambda self, other: ModInt(self.x + ModInt(other).x)
    __sub__ = lambda self, other: ModInt(self.x - ModInt(other).x)
    __mul__ = lambda self, other: ModInt(self.x * ModInt(other).x)
    __pow__ = lambda self, other: ModInt(pow(self.x, ModInt(other).x, MOD))
    __mod__ = lambda self, other: ModInt(self.x % ModInt(other).x)
    __truediv__ = lambda self, other: ModInt(self.x * pow(ModInt(other).x, MOD - 2, MOD))
    __floordiv__ = lambda self, other: ModInt(self.x // ModInt(other).x)
    __radd__ = lambda self, other: ModInt(other + self.x)
    __rsub__ = lambda self, other: ModInt(other - self.x)
    __rpow__ = lambda self, other: ModInt(pow(other, self.x, MOD))
    __rmod__ = lambda self, other: ModInt(other % self.x)
    __rmul__ = lambda self, other: ModInt(other * self.x)
    __rtruediv__ = lambda self, other: ModInt(other * pow(self.x, MOD - 2, MOD))
    __rfloordiv__ = lambda self, other: ModInt(other // self.x)

    __lt__ = lambda self, other: self.x < ModInt(other).x
    __gt__ = lambda self, other: self.x > ModInt(other).x
    __le__ = lambda self, other: self.x <= ModInt(other).x
    __ge__ = lambda self, other: self.x >= ModInt(other).x
    __eq__ = lambda self, other: self.x == ModInt(other).x
    __ne__ = lambda self, other: self.x != ModInt(other).x


def main():
    S = input()

    dp = [[0] * 13  for _   in range(len(S)-1)]
    dp[0] = [ModInt(0) for _ in range(13)]
    
    if S[0] == '?':
        for i in range(10):
            dp[0][i] = ModInt(1)
    else:
        dp[0][int(S[0])] = ModInt(1)

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

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









    pass
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
dp = [[0 for i in range(13)] for i in range(len(s))]
if s[-1] != "?":
    dp[0][int(s[-1]) % 13] += 1
else:
    for k in range(10):
        dp[0][k % 13] += 1

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s = input()
p = np.array([0]*13)
p[0] = 1

for si in range(len(s)):
  a = np.array([0]*13)
  if s[si] == '?':
    for j in range(10):
      for i in range(13):
        a[(i*10+j)%13] += p[i]
  else:
    c = int(s[si])
    for i in range(13):
      a[(i*10+c)%13] += p[i]
  p = np.mod(a,1000000007)
print(p[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def solve(s):
    MOD = 10 ** 9 + 7
    dp = np.zeros(13, dtype=np.int64)
    idx = [0] * 13
    for i in range(13):
        idx[i * 10 % 13] = i
    dp[0] = 1
    for c in s:
        if c == '?':
            tdp = dp[idx]
            ndp = tdp.copy()
            for i in range(1, 10):
                ndp += np.roll(tdp, i)
            ndp %= MOD
            dp = ndp
        else:
            i = int(c)
            dp = np.roll(dp[idx], i)
    return dp[5]


s = input()
print(solve(s))

Submission status: Time Limit Exceeded

Solution code:
S=input()
# S="".join(["?" for _ in range(10**5)])
# S = "??2??5"
# S= "?44"

MOD = 10**9+7
dp = [[0 for i in range(13)] for j in range(len(S)+1)]
dp[0][0] = 1
for t,ss in enumerate(S[::-1]):
    if t==0:
        tt = 1
    else:
        tt = (10*tt)%13
    if ss=="?":
        for i in range(13):
            for j in range(10):
                k = (j*tt+i)%13
                dp[t+1][k] +=dp[t][i]%MOD
    else:
        s = int(ss)
        for i in range(13):
            k = (s*tt+i)%13
            dp[t+1][k] += dp[t][i]%MOD

print(dp[t+1][5]%MOD)

Submission status: Time Limit Exceeded

Solution code:
s = input()
dp = [[0 for i in range(13)] for i in range(len(s))]
if s[-1] != "?":
    dp[0][int(s[-1]) % 13] += 1
else:
    for k in range(10):
        dp[0][k % 13] += 1

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def solve(s):
    MOD = 10 ** 9 + 7
    dp = np.zeros(13, dtype=np.int64)
    idx = [0] * 13
    for i in range(13):
        idx[i * 10 % 13] = i
    dp[0] = 1
    for c in s:
        ndp = np.zeros(13, dtype=np.int64)
        if c == '?':
            tdp = dp[idx]
            for i in range(10):
                ndp += np.roll(tdp, i)
            ndp %= MOD
        else:
            i = int(c)
            ndp = np.roll(dp[idx], i)
        dp = ndp
    return dp[5]


s = input()
print(solve(s))

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[0][0] = 1

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s = input()
p = np.array([0]*13)
p[0] = 1

for si in range(len(s)):
  a = np.array([0]*13)
  if s[si] == '?':
    for j in range(10):
      for i in range(13):
        a[(i*10+j)%13] += p[i]
  else:
    c = int(s[si])
    for i in range(13):
      a[(i*10+c)%13] += p[i]
  for i in range(13):
    p = np.mod(a,1000000007)
print(p[5])

Submission status: Time Limit Exceeded

Solution code:
import copy

s = input()
dp = [0 for i in range(13)]
dp[0] = 1
num = 0
c = 1000000007
mul = 1
for i in range(len(s) - 1, -1, -1):
    nextdp = [0 for i in range(13)]
    if s[i] == '?':
        for j in range(10):
            for k in range(13):
                nextdp[(j * mul + k) % 13] += dp[k]
                nextdp[(j * mul + k) % 13] %= c
    else:
        j = int(s[i])
        for k in range(13):
            nextdp[(j * mul + k) % 13] += dp[k]
            nextdp[(j * mul + k) % 13] %= c
    dp = copy.copy(nextdp)
    mul *= 10
    mul %= 13

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
'''
各桁ごとの*10**桁の13の余りの合計を考える
?000(mod13)=1000(mod13)*?(mod13)と考えられる
（前から）後ろの桁からDPをして?にぶつかるたびにたす
1?2?3を例とすると
0->3->?3->2?3->?2?3->1?2?3でDP
'''

S = input()
N = len(S)
mod = 13
dp = [[0 for i in range(13)] for j in range(N+1)]
dp[0][0] = 1

for i in range(N):
        if S[-i-1] == "?":
                m = 10 ** i
                for k in range(10):
                        p = (k*m)%13
                        for l in range(13):
                             dp[i+1][(p+l)%13]+=dp[i][l]

        else:
                k = int(S[-i-1])
                m = 10 ** i
                p = (k*m)%13
                for l in range(13):
                        dp[i+1][(p+l)%13]+=dp[i][l]


ans = int(dp[N][5])
ans = ans%(10**9+7)
print(ans)