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 = 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 = j - (s1*(10**i))%13
            if k < 0:
                k = k + 13
            else:
                k = k % 13
            dp[i][j] = dp[i-1][k]
    else:
        for j in range(13):
            for x in range(10):
                k = j - (x*((10**i)%13))%13
                if k < 0:
                    k = k + 13
                else:
                    k = k % 13
                dp[i][j] = (dp[i-1][k] + dp[i][j])%(10**9 + 7)
print(dp[n-1][5])

Submission status: Time Limit Exceeded

Solution code:
N = input()[::-1]
iv = 1
MOD = 10**9+7
dp = [0]*13
dp[0]=1
ls = [0]*13
for i in range(len(N)):
  x = N[i]
  
  if x=='?':
    for j in range(13):
      for h in range(10):
        ls[(h*iv+j)%13] += dp[j]
        
  else:
    x = int(x)
    for j in range(13):
      ls[(j+x*iv)%13]+=dp[j]
      
  for j in range(13):
    dp[j] = (ls[j]%MOD)
    ls[j]=0
  iv *= 10
  iv %= 13
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
#coding utf-8
S=list(input().strip())
S=[0]+S
mod=10**9+7

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

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

Submission status: Time Limit Exceeded

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

dp = [0] * 13 
dp[0] = 1
mul = 1
for i in range(0, N):
    next_dp = [0] * 13
    if S[N - i - 1] == '?':
        next_dp = [sum(dp[(j - k * mul) % 13] for k in range(10)) for j in range(13)]
    else:
        for j in range(13):
            k = int(S[N - i - 1])
            next_dp[(j + k * mul) % 13] = dp[j]
    dp = [d % MOD for d in next_dp]
    mul *= 10
    mul %= 13

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = 10 ** 9 + 7
dp = [0] * 13
dp[0] = 1
mul = 1

for i in reversed(range(len(s))):
    next_dp = [0] * 13
    if s[i] == "?":
        for j in range(10):
            for k in range(13):
                next_dp[(j * mul + k) % 13] += dp[k]
                next_dp[(j * mul + k) % 13] %= n
    else:
        for k in range(13):
            next_dp[(int(s[i]) * mul + k) % 13] += dp[k]
            next_dp[(int(s[i]) * mul + k) % 13] %= n
    dp = next_dp
    mul *= 10
    mul %= 13
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = 10 ** 9 + 7
dp = [0] * 13
dp[0] = 1
mul = 1

for i in reversed(range(len(s))):
    next_dp = [0] * 13
    if s[i] == "?":
        for j in range(10):
            for k in range(13):
                next_dp[(j * mul + k) % 13] += dp[k]
                next_dp[(j * mul + k) % 13] %= n
    else:
        for k in range(13):
            next_dp[(int(s[i]) * mul + k) % 13] += dp[k]
            next_dp[(int(s[i]) * mul + k) % 13] %= n
    dp = next_dp[:]
    mul *= 10
    mul %= 13
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
N = input()[::-1]
iv = 1
MOD = 10**9+7
pdp = [0 for i in range(13)]
pdp[0]=1
dp = [0 for i in range(13)]
for i in range(len(N)):
  x = N[i]
  if x=='?':
    for j in range(13):
      for h in range(10):
        dp[(h*iv+j)%13] += pdp[j]
    for j in range(13):
      pdp[j] = (dp[j]%MOD)
      dp[j] = 0
  else:
    x = int(x)
    for j in range(13):
      dp[(j+x*iv)%13]+=pdp[j]
    for j in range(13):
      pdp[j] = (dp[j]%MOD)
      dp[j]=0
  iv *= 10
  iv %= 13
print(pdp[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
def input():
    return sys.stdin.readline()[:-1]

S = [int(x) if x!="?" else -1 for x in input()]

div_num = 1000000007
arr = np.arange(13, dtype = np.uint64)
dp = np.zeros([2, 13], dtype = np.uint64)

div13_list = [1]
for ii in range(1, len(S)):
    n = div13_list[-1] * 10 % 13
    if n in div13_list:
        break
    else:
        div13_list.append(n)
div13_mat = np.array([div13_list] * 10, dtype = int)
div13_mat = (div13_mat * np.arange(10)[:, None] % 13).T

if S[-1] == -1:
    dp[0, :10] = 1
else:
    dp[0, S[-1]] = 1

for ii in range(1, len(S)):
    ind = -ii-1
    tmp = div13_mat[ii%6]
    if S[ind] == -1:
        for n in range(10):
            # res = (div13_list[ii] * n + arr) % 13
            # res = (tmp[n] + arr) % 13
            res = np.roll(arr, -tmp[n])
            dp[1, res] += dp[0, arr]
    else:
        # res = (div13_list[ii] * S[ind] + arr) % 13
        # res = (tmp[S[ind]] + arr) % 13
        res = np.roll(arr, -tmp[S[ind]])
        dp[1, res] += dp[0, arr]
    dp[0] = dp[1] % div_num
    dp[1] = 0


print (dp[0, 5])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# from tqdm import tqdm

S = input()
N = len(S)
MOD = 10 ** 9 + 7

dp = [0] * 13 
next_dp = [0] * 13
dp[0] = 1
mul = 1
for i in range(0,N) : # tqdm(range(0, N)):
    if S[N - i - 1] == '?':
        for k in range(10):
            for j in range(13):
                next_dp[(j + k * mul) % 13] += dp[j]
                next_dp[(j + k * mul) % 13] %= MOD
    else:
        for j in range(13):
            k = int(S[N - i - 1])
            next_dp[(j + k * mul) % 13] = dp[j]
            next_dp[(j + k * mul) % 13] %= MOD
    dp = next_dp
    next_dp = [0] * 13
    mul *= 10
    mul %= 13

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
def input():
    return sys.stdin.readline()[:-1]

S = [int(x) if x!="?" else -1 for x in input()]

div_num = 1000000007
arr = np.arange(13, dtype = np.uint64)
dp = np.zeros([2, 13], dtype = np.uint64)

div13_list = [1]
for ii in range(1, len(S)):
    n = div13_list[-1] * 10 % 13
    if n in div13_list:
        break
    else:
        div13_list.append(n)
div13_mat = np.array([div13_list] * 10, dtype = int)
div13_mat = (div13_mat * np.arange(10)[:, None] % 13).T
# print (div13_mat)

if S[-1] == -1:
    dp[0, :10] = 1
else:
    dp[0, S[-1]] = 1

for ii in range(1, len(S)):
    ind = -ii-1
    tmp = div13_mat[ii%6]
    if S[ind] == -1:
        for n in range(10):
            # res = (div13_list[ii] * n + arr) % 13
            res = (tmp[n] + arr) % 13
            dp[1, res] += dp[0, arr]
    else:
        # res = (div13_list[ii] * S[ind] + arr) % 13
        res = (tmp[S[ind]] + arr) % 13
        dp[1, res] += dp[0, arr]
    dp[0] = dp[1] % div_num
    dp[1] = 0


print (dp[0, 5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
def input():
    return sys.stdin.readline()[:-1]

import time

S = [int(x) if x!="?" else -1 for x in input()]
# print (S)

# t1 = time.time()

div_num = 1000000007
arr = np.arange(13, dtype = np.uint64)
dp = np.zeros([2, 13], dtype = np.uint64)

# t2 = time.time()

div13_list = [1]
for ii in range(1, len(S)):
    div13_list.append(div13_list[-1] * 10 % 13)

if S[-1] == -1:
    dp[0, :10] = 1
else:
    dp[0, S[-1]] = 1

# t3 = time.time()

for ii in range(1, len(S)):
    ind = -ii-1
    if S[ind] == -1:
        for n in range(10):
            res = (div13_list[ii] * n + arr) % 13
            dp[1, res] += dp[0, arr]
    else:
        res = (div13_list[ii] * S[ind] + arr) % 13
        dp[1, res] += dp[0, arr]
    dp[0] = dp[1] % div_num
    dp[1] = 0

# t4 = time.time()

print (dp[0, 5])


# print (t2-t1)
# print (t3-t2)
# print (t4-t3)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
def input():
    return sys.stdin.readline()[:-1]

S = input()

div_num = 1000000007
arr = np.arange(13, dtype = int)
dp = np.zeros([len(S), 13], dtype = int)

div13_list = [1]
for ii in range(1, len(S)):
    div13_list.append(div13_list[-1] * 10 % 13)

if S[-1] == "?":
    for ii in range(10): dp[0, ii] = 1
else:
    dp[0, int(S[-1])] = 1

for ii in range(1, len(S)):
    ind = -ii-1
    if S[ind] == '?':
        for n in range(10):
            # res = (((10 ** ii) * n) % 13 + arr) % 13
            res = (div13_list[ii] * n + arr) % 13
            dp[ii, res] += dp[ii - 1, arr]
            dp[ii, res] %= div_num
    else:
        # res = (((10 ** ii) * int(S[ind])) % 13 + arr) % 13
        res = (div13_list[ii] * int(S[ind]) + arr) % 13
        dp[ii, res] += dp[ii - 1, arr]
        dp[ii, res] %= div_num

print (dp[-1, 5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
def input():
    return sys.stdin.readline()[:-1]

S = input()

div_num = 1000000007
arr = np.arange(13, dtype = int)
# dp = [[0 for _ in range(13)] for _ in range(len(S))]
dp = np.zeros([len(S), 13], dtype = int)

if S[-1] == "?":
    for ii in range(10): dp[0, ii] = 1
else:
    dp[0, int(S[-1])] = 1

for ii in range(1, len(S)):
    ind = -ii-1
    if S[ind] == '?':
        for n in range(10):
            res = (((10 ** ii) * n) % 13 + arr) % 13
            dp[ii, res] += dp[ii - 1, arr]
            dp[ii, res] %= div_num
    else:
        res = (((10 ** ii) * int(S[ind])) % 13 + arr) % 13
        dp[ii, res] += dp[ii - 1, arr]
        dp[ii, res] %= div_num

print (dp[-1, 5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
def input():
    return sys.stdin.readline()[:-1]

S = input()

div_num = 10 ** 9 + 7
arr = np.arange(13, dtype = int)
# dp = [[0 for _ in range(13)] for _ in range(len(S))]
dp = np.zeros([len(S), 13], dtype = int)

if S[-1] == "?":
    for ii in range(10): dp[0, ii] = 1
else:
    dp[0, int(S[-1])] = 1

for ii in range(1, len(S)):
    ind = -ii-1
    if S[ind] == '?':
        for n in range(10):
            res = ((10 ** ii) * n) % 13
            res = (arr + res) % 13
            for jj in range(13):
                dp[ii, res[jj]] += dp[ii - 1, jj]
                if dp[ii, res[jj]] > div_num: dp[ii, res[jj]] -= div_num
    else:
        res = ((10 ** ii) * int(S[ind])) % 13
        res = (arr + res) % 13
        for jj in range(13):
            dp[ii, res[jj]] += dp[ii - 1, jj]
            if dp[ii, res[jj]] > div_num: dp[ii, res[jj]] -= div_num

print (dp[-1, 5])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
S = str(input())
MOD = 1000000007

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

print(dp[5] % MOD)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
S = str(input())
MOD = 1000000007

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

print(dp[5] % MOD)

Submission status: Time Limit Exceeded

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

dp[0][0] = 1

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

Submission status: Time Limit Exceeded

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

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

cnt = 1
for i, c in enumerate(S[::-1], 1):
    t = a[i]
    for j in range(13):
        if c == "?":
            for k in range(10):
                nj = (k*t+j) % 13
                dp[i][nj] = dp[i][nj] + dp[i-1][j]
                dp[i][nj] %= MOD
        else:
            nj = (int(c)*t+j) % 13
            dp[i][nj] = dp[i][nj] + dp[i-1][j]
            dp[i][nj] %= MOD
print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
S = (stdin.readline().rstrip())
dp = [[0]*13 for i in range(len(S)+1)]
MOD = 10**9+7

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

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
S = (stdin.readline().rstrip())
dp = [[0]*13 for i in range(len(S)+1)]
MOD = 10**9+7

S = list(reversed(S))
a = [0] + [(10**i) % 13 for i in range(len(S))]
dp[0][0] = 1

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

Submission status: Time Limit Exceeded

Solution code:
import math, heapq
from operator import itemgetter as ig
from collections import defaultdict as dd
# 定数
INF = float("inf")
MOD = int(1e9 + 7)
# データ構造：ヒープ
class heapque:
    def __init__(self, *args):
        self.que = []
        for arg in args:
            self.push(arg)
    def push(self, v):
        heapq.heappush(self.que, v)
    def pop(self):
        return heapq.heappop(self.que)
# 最大公約数 / 最小公倍数
def gcd(v1, v2):
    if v2 == 0:
        return v1
    return gcd(v2, v1 % v2)
def lcm(v1, v2):
    return (v1 // gcd(v1, v2)) * v2
# 二分探索
def bsr(a, v, lo=0, hi=None):
    if hi == None:
        hi = len(a) - 1
    if hi < lo:
        return lo
    mi = (lo + hi) // 2
    if v < a[mi]:
        return bsr(a, v, lo, mi - 1)
    else:
        return bsr(a, v, mi + 1, hi)
# Union-Find木
class uft:
    def __init__(self, n):
        self.height = [1] * n
        self.group = [-1] * n
    def root(self, v):
        if self.group[v] < 0:
            return v
        self.group[v] = self.root(self.group[v])
        return self.group[v]
    def size(self, v):
        return - self.group[self.root(v)]
    def merge(self, v1, v2):
        v1, v2 = self.root(v1), self.root(v2)
        if v1 == v2:
            return
        if self.height[v1] < self.height[v2]:
            self.group[v2] += self.group[v1]
            self.group[v1] = v2
            self.height[v2] = max(self.height[v1] + 1, self.height[v2])
        else:
            self.group[v1] += self.group[v2]
            self.group[v2] = v1
            self.height[v1] = max(self.height[v1] , self.height[v2] + 1)

def main():
    S = input()
    dp = [[0 for _ in range(13)] for _ in range(len(S) + 1)]
    dp[0][0] = 1
    for i, s in enumerate(S):
        i += 1
        loop = range(10) if s == "?" else [int(s)]
        for n in range(13):
            for m in loop:
                dp[i][(n * 10 + m) % 13] += dp[i - 1][n]
                dp[i][(n * 10 + m) % 13] %= MOD
    print(dp[-1][5])

main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
S=input()
dp_old=[0]*13
dp_new=[0]*13
dp_old[0]=1
for c in S:
    if c == '?':
        for i in range(10):
            for j in range(13):
                dp_new[(j*10+i)%13]+=dp_old[j]
    else:
        for i in range(13):
            dp_new[(i*10+int(c))%13]+=dp_old[i]
    dp_old = [i%MOD for i in dp_new]
    dp_new = [0]*13
print(dp_old[5])

Submission status: Time Limit Exceeded

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

dp = [[0 for _ in range(14)] for _ in range(n + 1)]

dp[0][0] = 1
for i, c in enumerate(s):
    for k in range(13):
        if c == '?':
            for l in range(10):
                dp[i + 1][(k * 10 + l) % 13] += dp[i][k]
        else:
            dp[i + 1][(k * 10 + int(c)) % 13] += dp[i][k]

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

print(dp[n][5])

Submission status: Time Limit Exceeded

Solution code:
S=raw_input()
l=len(S)

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

mod=10**9+7

dp2=[ 0 for _ in range(13) ]

for i in range(1,l+1):
	dp2=[0]*13
	for j in range(13):
		if dp[j]!=0:
			if S[i-1]=="?":
				for k in range(10):
					next=(k*pow(10,l-i,13)+j)%13 
					dp2[next]+=dp[j]
					dp2[next]%=mod
			else:
				k=int(S[i-1])
				next=(k*pow(10,l-i,13)+j)%13
				dp2[next]+=dp[j]
				dp2[next]%=mod
	dp=dp2

print dp[5]

Submission status: Time Limit Exceeded

Solution code:
S=raw_input()
l=len(S)

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

mod=10**9+7


for i in range(1,l+1):
	dp2=[ 0 for _ in range(13) ]
	for j in range(13):
		if dp[j]!=0:
			if S[i-1]=="?":
				for k in range(10):
					next=(k*pow(10,l-i,13)+j)%13 
					dp2[next]+=dp[j]
					dp2[next]%=mod
			else:
				k=int(S[i-1])
				next=(k*pow(10,l-i,13)+j)%13
				dp2[next]+=dp[j]
				dp2[next]%=mod
	dp=dp2

print dp[5]

Submission status: Time Limit Exceeded

Solution code:
S=raw_input()
l=len(S)

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

mod=10**9+7


for i in range(1,l+1):
	dp2=[ 0 for _ in range(13) ]
	for j in range(13):
		if dp[j]!=0:
			if S[i-1]=="?":
				for k in range(10):
					dp2[ (k*pow(10,l-i,13)+j)%13 ]+=dp[j]
					dp2[ (k*pow(10,l-i,13)+j)%13 ]%=mod
			else:
				k=int(S[i-1])
				dp2[ (k*pow(10,l-i,13)+j)%13 ]+=dp[j]
				dp2[ (k*pow(10,l-i,13)+j)%13 ]%=mod
	dp=dp2

print dp[5]

Submission status: Time Limit Exceeded

Solution code:
S=raw_input()
l=len(S)

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

mod=10**9+7


for i in range(1,l+1):
	for j in range(13):
		if dp[i-1][j]!=0:
			if S[i-1]=="?":
				for k in range(10):
					dp[i][ (k*pow(10,l-i,13)+j)%13 ]+=dp[i-1][j]
					dp[i][ (k*pow(10,l-i,13)+j)%13 ]%=mod
			else:
				k=int(S[i-1])
				dp[i][ (k*pow(10,l-i,13)+j)%13 ]+=dp[i-1][j]
				dp[i][ (k*pow(10,l-i,13)+j)%13 ]%=mod

print dp[-1][5]

Submission status: Time Limit Exceeded

Solution code:
S=raw_input()
l=len(S)

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

mod=10**9+7


for i in range(1,l+1):
	for j in range(13):
		if dp[i-1][j]!=0:
			if S[i-1]=="?":
				for k in range(10):
					dp[i][ (k*pow(10,l-i)+j)%13 ]+=dp[i-1][j]
					dp[i][ (k*pow(10,l-i)+j)%13 ]%=mod
			else:
				k=int(S[i-1])
				dp[i][ (k*pow(10,l-i)+j)%13 ]+=dp[i-1][j]
				dp[i][ (k*pow(10,l-i)+j)%13 ]%=mod

print dp[-1][5]

Submission status: Time Limit Exceeded

Solution code:
s = input()

array = [[0 for i in range(13)] for j in range(len(s)+1)] 

array[0][0] = 1
for i in range(0,len(s)):
  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):
      array[i+1][(k*10+j) % 13] += array[i][k]
      
  for j in range(13):
    array[i+1][j] %= 1000000007
    
print(array[len(s)][5])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
all_remains = [0]*13
for digits, s in enumerate(S[::-1]):
    temp_remains = [0]*13     
    if s == '?':
        if digits == 0:
            for i in range(10):
                temp_remains[i % 13] += 1
        else:
            for i in range(10):
                r = i * (10**digits) % 13
                for j in range(13):
                    temp_remains[ (j + r) % 13] += all_remains[j]
    else:
        if digits == 0:
                temp_remains[int(s)] += 1
        else:
            n = int(s)*(10**digits) % 13
            for j in range(13):
                temp_remains[(j + n) % 13] += all_remains[j]
    all_remains = temp_remains
print(all_remains[5]%(10**9+7))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

dp = [[0 for _ in range(13)] for _ in range(2)]
dp[1][0] = 1
for c in S:
    dp[0], dp[1] = dp[1], dp[0]
    for i in range(10):
        if c != '?' and int(c) != i:
            continue
        for j in range(13):
            dp[1][(j*10+i)%13] += dp[0][j]
    
    for i in range(13):
        dp[1][i] %= P
        dp[0][i] = 0

print(dp[1][5])

Submission status: Time Limit Exceeded

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

dp = [[0 for _ in range(13)] for _ in range(len(S)+1)]
dp[0][0] = 1
for n, c in enumerate(S):
    for i in range(10):
        if c != '?' and int(c) != i:
            continue
        for j in range(13):
            dp[n+1][(j*10+i)%13] += dp[n][j]
    
    for i in range(13):
        dp[n+1][i] %= P

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

Submission status: Time Limit Exceeded

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

dp = [[0 for _ in range(13)] for _ in range(len(S)+1)]
dp[0][0] = 1
for n, c in enumerate(S):
    for i in range(10):
        if c != '?' and int(c) != i:
            continue
        for j in range(13):
            dp[n+1][(j*10+i)%13] += dp[n][j]

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

Submission status: Time Limit Exceeded

Solution code:
def p_d():
    S = input()
    N = 13

    dp = [0] * N
    dp[0] = 1

    mul = 1
    mod = 10 ** 9 + 7

    for i in reversed(range(len(S))):
        nextDP = [0] * N
        c = S[i]
        if c == "?":
            for k in range(10):  # 数字[0-9]
                for j in range(N):
                    nextDP[(k * mul + j) % N] += dp[j]
                    nextDP[(k * mul + j) % N] %= mod
        else:
            k = int(c)
            for j in range(N):
                nextDP[(k * mul + j) % N] += dp[j]
                nextDP[(k * mul + j) % N] %= mod
        mul *= 10
        mul %= N
        dp = nextDP

    print(int(dp[5]))


if __name__ == '__main__':
    p_d()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def p_d():
    S = input()
    N = 13

    dp = np.zeros(N)
    dp[0] = 1

    mul = 1
    mod = 10 ** 9 + 7

    for i in reversed(range(len(S))):
        nextDP = np.zeros(N)
        c = S[i]
        if c == "?":
            for k in range(10):  # 数字[0-9]
                for j in range(N):
                    nextDP[(k * mul + j) % N] += dp[j]
                    nextDP[(k * mul + j) % N] %= mod
        else:
            k = int(c)
            for j in range(N):
                nextDP[(k * mul + j) % N] += dp[j]
                nextDP[(k * mul + j) % N] %= mod
        mul *= 10
        mul %= N
        dp = nextDP

    print(int(dp[5]))


if __name__ == '__main__':
    p_d()

Submission status: Time Limit Exceeded

Solution code:
P=[1,10,9,12,3,4]
m=10**9+7
def f(A,p,N):
    if p==0:return [1&(i in N) for i in range(13)]
    p%=6
    B=[0]*13
    for n in N:
        for i in range(13):
            c=(i+(n*P[p]))%13
            B[c]=(B[c]+A[i])%m
    return B

S=reversed(input())
A=[0]
for p,s in enumerate(S):
    if s=="?":A=f(A,p,range(10))
    else:A=f(A,p,[int(s)])
print(A[5])

Submission status: Time Limit Exceeded

Solution code:
S = input()
memo_ls = [[0 for j in range(13)] for i in range(len(S) + 1)]
memo_ls[0][0] = 1
for i in range(len(S)):
    for _ in range(10):
        if S[i] != "?" and int(S[i]) != _:
            continue
        for j in range(13):
            memo_ls[i + 1][(j * 10 + _) % 13] += memo_ls[i][j]
    for j in range(13):
        memo_ls[i + 1][j] %= 10**9+7

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


MOD = int(1e09 + 7)

S = list(input())
N = len(S)
dp = np.zeros((N+1, 13), dtype=np.int64)

dp[0,0] = 1
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] %= MOD

print(dp[N][5])

Submission status: Time Limit Exceeded

Solution code:
P=[1,10,9,12,3,4]
def f(A,p,N):
    if p==0:return [1&(i in N) for i in range(13)]
    B=[0]*13
    for n in N:
        for i in range(13):
            c=(i+(n*P[p%6]))%13
            B[c]=(B[c]+A[i])%(10**9+7)
    return B
S=reversed(input())
A=[0]
for p,s in enumerate(S):
    if s=="?":A=f(A,p,range(10))
    else:A=f(A,p,[int(s)])
print(A[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def main():
    n = 13
    mod = 1000000007
    r = 5
    in_str = input()

    amari_list = amari(n)
    l = len(amari_list)

    ans_list = initial(in_str[-1:], n)

    for i, s in enumerate(reversed(in_str)):
        if i == 0:
            continue
        if s == "?":
            shift_list = np.array(
                [np.roll(ans_list, j * amari_list[i % l] % n) for j in range(10)], dtype='int64')
            ans_list = np.mod(np.sum(shift_list, axis=0), mod)

        else:
            t = int(s) * amari_list[i % l] % n
            ans_list = np.roll(ans_list, t)

    print(ans_list[r] % mod)


def initial(s, n):
    if s == "?":
        return np.array([1 if i < 10 else 0 for i in range(n)], dtype='int64')
    else:
        return np.array([1 if i == int(s) else 0 for i in range(n)], dtype='int64')


def amari(n):
    ret = []
    for i in range(n+1):
        r = (10**i) % n
        if r in ret:
            return ret
        else:
            ret.append(r)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def main():
    n = 13
    mod = 1000000007
    r = 5
    in_str = input()

    amari_list = amari(n)
    l = len(amari_list)

    ans_list = initial(in_str[-1:], n)

    for i, s in enumerate(reversed(in_str)):
        if i == 0:
            continue
        if s == "?":
            shift_list = np.array([shift(j * amari_list[i % l] % n, ans_list)
                                   for j in range(10)], dtype='int64')

            ans_list = np.mod(np.sum(shift_list, axis=0), mod)

        else:
            t = int(s) * amari_list[i % l] % n
            ans_list = shift(t, ans_list)

    print(ans_list[r] % mod)


def shift(r, num_list):
    l = len(num_list)
    return np.array([num_list[(i + l - r) % l] for i in range(l)], dtype='int64')


def initial(s, n):
    if s == "?":
        return np.array([1 if i < 10 else 0 for i in range(n)], dtype='int64')
    else:
        return np.array([1 if i == int(s) else 0 for i in range(n)], dtype='int64')


def amari(n):
    ret = []
    for i in range(n+1):
        r = (10**i) % n
        if r in ret:
            return ret
        else:
            ret.append(r)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

# ans_list[i] : 13で割った余りがiの個数。これを入力の1桁目から更新していく。1桁目は以下


def main():
    n = 13
    mod = 1000000007
    r = 5
    in_str = input()

    amari_list = amari(n)
    l = len(amari_list)

    ans_list = initial(in_str[-1:], n)

    for i, s in enumerate(reversed(in_str)):
        if i == 0:
            continue
        if s == "?":
            shift_list = [shift(j * amari_list[i % l] % n, ans_list)
                          for j in range(10)]

            ans_list = add(shift_list, mod)
        else:
            t = int(s) * amari_list[i % l] % n
            ans_list = shift(t, ans_list)

    print(ans_list[r] % mod)


def shift(r, num_list):
    l = len(num_list)
    return [num_list[(i + l - r) % l] for i in range(l)]


def add(num_list, mod):
    return [sum([num_list[i][j] for i in range(len(num_list))]) % mod for j in range(len(num_list[0]))]


def initial(s, n):
    if s == "?":
        return [1 if i < 10 else 0 for i in range(n)]
    else:
        return [1 if i == int(s) else 0 for i in range(n)]


def amari(n):
    ret = []
    for i in range(n+1):
        r = (10**i) % n
        if r in ret:
            return ret
        else:
            ret.append(r)


if __name__ == '__main__':
    main()