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:
from heapq import heappush, heappop
import re
from collections import deque
import sys
import math
input = sys.stdin.readline


def int_raw():
    return int(input())


def ss_raw():
    return input().split()


def ints_raw():
    return tuple(map(int, ss_raw()))


DIV = 10**9+7


def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def ncr(n, r, mod=DIV):
	r = min(r, n-r)
	ret = 1
	for i in range(1, r+1):
		ret = ret * (n-i+1) % mod
		ret = ret * mod_inv(i, mod) % mod
	return ret


def main():
    S = input().rstrip("\n")
    dp = [[0 for i in range(13)] for i in range(len(S)+1)]
    dp [0][0] = 1
    modi = 1%13
    for i in range(1,len(S)+1):
        modi = (10**(i-1)) %13
        s = S[len(S)-i]
        if s!= '?':
            mod_q = (int(s)*modi)%13
            for k in range(13):
                dp[i][(k+mod_q) % 13] = (dp[i][(k+mod_q) % 13]+dp[i-1][k]) % DIV
        else:
            for j in range(10):
                mod_q = (j*modi) % 13
                for k in range(13):
                    dp[i][(k+mod_q) % 13] = (dp[i]
                                             [(k+mod_q) % 13]+dp[i-1][k]) % DIV
        modi = (modi*10)%13
    return dp[len(S)][5]
print(main())

Submission status: Time Limit Exceeded

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

dp = [[0 for _ in range(13)] for _ in range(len(S) + 1)]  # dp[digit][d] = digit桁までの mod=d の数
dp[0][0] = 1

for digit in range(1, len(S) + 1) :
    digitMask = 10**(digit - 1)
    if(S[-digit] == '?') :
        for d in range(13) :
            for k in range(10) :
                dp[digit][d] = (dp[digit][d] + dp[digit - 1][(d - k * digitMask) % 13]) % MOD
    else :
        a = int(S[-digit])
        for d in range(13) :
            dp[digit][d] = (dp[digit][d] + dp[digit - 1][(d - a * digitMask) % 13]) % MOD

ans = (dp[len(S)][5]) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = []
mod = int(10**9+7)

for k in range(6):
    T.append([])
    r = 10**k
    for j in range(10):
        T[-1].append(j*r%13)

dp = [1]+[0]*12
k = (len(S)-1)%6
for s in S:
    dp_new = [0]*13
    if s=='?':
        for r in range(10):
            m = T[k][r]
            for i in range(13):
                dp_new[(i+m)%13] += dp[i]
    else:
        m = T[k][int(s)]
        for i in range(13):
            dp_new[(i+m)%13] = dp[i]
    dp = [d%mod for d in dp_new]
    k=(k+5)%6

print(dp[5]%mod)

Submission status: Time Limit Exceeded

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

s = input().rstrip()

keta_all = len(s)
amari_cnt_old = [1] + [0] * 12

for i,a in enumerate(s):
	keta_cur = keta_all - i-1
	amari_cnt_new = [0] * 13
	
	if a == "?":
		for j in range(10):
			amari_cur = (j * (10**keta_cur))%13
			for amari_old,amari_cnt_tmp in enumerate(amari_cnt_old):
				amari_cnt_new[(amari_cur+amari_old)%13] += (amari_cnt_tmp)
	else:
		amari_cur = ((int(a)) * (10**keta_cur))%13
		for amari_old,amari_cnt_tmp in enumerate(amari_cnt_old):
			amari_cnt_new[(amari_cur+amari_old)%13] += (amari_cnt_tmp)
	
	amari_cnt_old = amari_cnt_new

print((amari_cnt_old[5]%MOD))

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
q = []
A = 13-5
for i in range(N-1,-1,-1):
    if S[i] == '?':
        q.append(N-i-1)
    else:
        A = (A+int(S[i])*(10**(N-i-1)))%13
DP= [[0]*13 for i in range(len(q)+1)]
DP[0][A] = 1
B = [[0]*13 for i in range(13)]
for i in range(13):
    for j in range(13):
        B[i][j] = (i*j)%13
T = [1,10,9,12,3,4]
for i in range(len(q)):
    for j in range(13):
        for k in range(10):
            DP[i+1][(j+k*T[q[i]%6])%13] = (DP[i+1][(j+k*T[q[i]%6])%13]+DP[i][j])%(10**9+7)
print(DP[-1][0])

Submission status: Time Limit Exceeded

Solution code:
s = input()
mod = 10 ** 9 + 7
dp = []
for i in range(13):
    temp = [0] * len(s)
    dp.append(temp)
# j桁目がxのとき13で割ったあまり
def amari(x, j):
    if x != "?":
        x = int(x)
        return [(10 ** j % 13) * x]
    else:
        return [(10 ** j % 13) * x for x in range(10)]
for i in amari(s[-1], 0):
    dp[i][0] = 1
for i in range(1, len(s)):
    for j in range(13):
        for k in amari(s[-i-1], i):
            dp[j][i] += dp[(j - k) % 13][i - 1]
            dp[j][i] %= mod
print(dp[5][len(s) - 1])

Submission status: Time Limit Exceeded

Solution code:
S = input()
le = len(S)

mod = 10**9 + 7

mo = 1

dp = ([1]*10 if S[-1] == "?" else [int(x == int(S[-1])) for x in range(10)]) + [0]*3

i = 1
while i != le:
    mo = (mo * 10)%13
    a = [0]*13
    if S[-i-1] == "?":
        j = 0
        while j != 10:
            k = 0
            while k != 13:
                a[(k+mo*j)%13] += dp[k]
                a[(k+mo*j)%13] %= mod
                k += 1
            j += 1
    else:
        j = int(S[-i-1])
        k = 0
        while k != 13:
            a[(k+mo*j)%13] += dp[k]
            a[(k+mo*j)%13] %= mod
            k += 1
    dp = a
    i += 1

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from functools import lru_cache

PRIME = 10 ** 9 + 7


@lru_cache(maxsize=None)
def digitmod13(y):
    if y == 0:
        return 1
    elif y == 1:
        return 10 % 13
    elif y % 2 == 0:
        return digitmod13(y // 2) ** 2 % 13
    else:
        return digitmod13(y // 2) ** 2 * 10 % 13


def main():
    S = input()
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(N)]
    S = S[::-1]
    
    # init
    first = S[0]
    if first == '?':
        for k in range(10):
            dp[0][k] = 1
    else:
        first = int(first)
        dp[0][first] = 1
    
    # dp
    for i in range(1, N):
        c = S[i]
        if c == '?':
            for d in range(13):
                for k in range(10):
                    dp[i][(d + k * digitmod13(i)) % 13] += dp[i - 1][d]
                    dp[i][(d + k * digitmod13(i)) % 13] %= PRIME
        else:
            c = int(c)
            for d in range(13):
                dp[i][(d + c * digitmod13(i)) % 13] += dp[i - 1][d]
                dp[i][(d + c * digitmod13(i)) % 13] %= PRIME
    
    print(dp[N - 1][5] % PRIME)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
q = []
A = 13-5
for i in range(N-1,-1,-1):
    if S[i] == '?':
        q.append(N-i-1)
    else:
        A = (A+int(S[i])*(10**(N-i-1)))%13
DP= [[0]*13 for i in range(len(q)+1)]
DP[0][A] = 1
B = [[0]*13 for i in range(13)]
for i in range(13):
    for j in range(13):
        B[i][j] = (i*j)%13
T = [1,10,9,12,3,4]
for i in range(len(q)):
    for j in range(13):
        for k in range(10):
            DP[i+1][(j+k*T[q[i]%6])%13] = (DP[i+1][(j+k*T[q[i]%6])%13]+DP[i][j])%(10**9+7)
print(DP[-1][0])

Submission status: Time Limit Exceeded

Solution code:
S = input()
le = len(S)
S = S[::-1]

mod = 10**9 + 7

mo = 1

dp = ([1]*10 if S[0] == "?" else [int(x == int(S[0])) for x in range(10)]) + [0]*3

i = 1
while i != le:
    mo = (mo * 10)%13
    a = [0]*13
    if S[i] == "?":
        j = 0
        while j != 10:
            k = 0
            while k != 13:
                a[(k+mo*j)%13] += dp[k]
                a[(k+mo*j)%13] %= mod
                k += 1
            j += 1
    else:
        j = int(S[i])
        k = 0
        while k != 13:
            a[(k+mo*j)%13] += dp[k]
            a[(k+mo*j)%13] %= mod
            k += 1
    dp = a
    i += 1

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
S = input()
T = []
mod = int(10**9+7)

for k in range(6):
    T.append([])
    r = 10**k
    for j in range(10):
      	T[-1].append(j*r%13)
	
dp = [1]+[0]*12
k = len(S)-1
for s in S:
    dp_new = [0]*13
    if s=='?':
        for r in range(10):
            m = T[k%6][r]
            for i in range(13):
                dp_new[(i+m)%13] += dp[i] % mod
    else:
        m = T[k%6][int(s)]
        for i in range(13):
            dp_new[(i+m)%13] = dp[i]
    dp = dp_new
    k-=1

print(dp[5]%mod)

Submission status: Time Limit Exceeded

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

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

MOD = 10 ** 9 + 7
s = input().strip()
n = len(s)
if s[-1] == "?":
    tmp = [1 for i in range(10)] + [0 for i in range(3+13*(n-1))]

else:
    tmp = [0 for i in range(13*n)]
    # print("-------------------")
    # print(s[-1])
    # print(int(s[-1]))
    tmp[int(s[-1])] = 1
# print(len(tmp))
keta = 1
for kt, c in enumerate(s[::-1][1:]):
    keta = (keta * 10) % 13
    
    if c != "?":
        seni = int(c) * keta
        for j in range(13):
            tmp[(j + seni) % 13 + (kt + 1) * 13] += tmp[kt * 13 + j] % MOD
    else:
        for isure in range(10):
            seni = isure * keta
            for j in range(13):
                tmp[(j + seni) % 13 + (kt + 1) * 13] += tmp[kt * 13 + j] % MOD
                # print(nw)

    # print(tmp[(13*kt):13*(kt+1)])
    # tmp = [num % MOD for num in nw]
    # tmp = nw
print(tmp[-8] % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

if __name__ == '__main__':
    s = input()
    table = [[0] * 13 for _ in range(len(s) + 1)]
    table[0][0] = 1
    for i, c in enumerate(s):
        if c == '?':
            for j in range(13):
                for l in range(10):
                    k = (10 * j + l) % 13
                    table[i + 1][k] += table[i][j]
                    table[i + 1][k] %= MOD
        else:
            l = ord(c) - ord('0')
            for j in range(13):
                k = (10 * j + l) % 13
                table[i + 1][k] = table[i][j]
    print(table[len(s)][5])

Submission status: Time Limit Exceeded

Solution code:
S = input()

s = list(S)

s.reverse()



lis = [0] * 13
lis[0] = 1

for i in range(len(S)):

    nlis = [0] * 13

    if s[i] == "?":

        for j in range(10):

            for k in range(13):

                nlis[ (k + (j * (10**i))) % 13] += lis[k]

    else:

        now = int(s[i])

        for k in range(13):

            nlis[ (k + (now * (10 ** i))) % 13 ] += lis[k]


    for j in range(len(nlis)):
      lis[j] = nlis[j]


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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *

mod = 10**9+7
def rec(k, m):
    if k == N:
        return m == 5
    if memo[k][m] != -1:
        return memo[k][m]
    res = 0
    d = D[N-k-1]
    if S[k] != '?':
        res += rec(k+1, (m+int(S[k])*d)%13)
    else:
        for i in range(10):
            res += rec(k+1, (m+i*d)%13)
    res %= mod
    memo[k][m] = res
    return res

S = input()
N = len(S)
D = [None] * N
t = 1
for i in range(N):
    D[i] = t % 13
    t = t * 10 % 13
memo = [[-1] * 13 for i in range(N+1)]
# for k in range(N):
#     if S[k] != '?':
#         dp[]
#         for  in range(0, 1):
print(rec(0, 0))

Submission status: Time Limit Exceeded

Solution code:
s = input()

items = dict()
for i in range(len(s)):
    if s[i] != "?":
        items[i] = s[i]

cnt = 0
for i in range(10**len(s)):
    if i % 13 != 5:
        continue
    flg = True
    item = str(i).zfill(len(s))
    for key, val in items.items():
        if item[key] != val:
            flg = False
            break
    if flg:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

s = ns()
n = len(s)
MOD = 10**9 + 7

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

for i, si in enumerate(s):
    if si == '?':
        for k in range(10):
            for j in range(13):
                dp[i+1][(10*j + k) % 13] += dp[i][j]
                dp[i + 1][(10 * j + k) % 13] %= MOD

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

print(dp[n][5])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from functools import lru_cache

PRIME = 10 ** 9 + 7


@lru_cache(maxsize=None)
def digitmod13(n):
    return (10 ** n) % 13


def main():
    S = input()
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(N)]
    S = S[::-1]
    # init
    first = S[0]
    if first == '?':
        for k in range(10):
            dp[0][k] = 1
    else:
        first = int(first)
        dp[0][first] = 1
    for i in range(1, N):
        c = S[i]
        if c == '?':
            for d in range(13):
                for k in range(10):
                    dp[i][(d + k * digitmod13(i)) % 13] += dp[i - 1][d]
        else:
            c = int(c)
            for d in range(13):
                dp[i][(d + c * digitmod13(i)) % 13] += dp[i - 1][d]
        for d in range(13):
            dp[i][d] %= PRIME
    
    print(dp[N - 1][5] % PRIME)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

MOD = 10 ** 9 + 7
s = input().strip()
n = len(s)
if s[-1] == "?":
    tmp = [1 for i in range(10)] + [0 for i in range(3+13*(n-1))]

else:
    tmp = [0 for i in range(13*n)]
    # print("-------------------")
    # print(s[-1])
    # print(int(s[-1]))
    tmp[int(s[-1])] = 1
# print(len(tmp))
keta = 1
for kt, c in enumerate(s[::-1][1:]):
    keta = (keta * 10) % 13
    nw = [0 for i in range(13)]
    if c != "?":
        seni = int(c) * keta
        for j in range(13):
            tmp[(j + seni) % 13 + (kt + 1) * 13] += tmp[kt * 13 + j] % MOD
    else:
        for isure in range(10):
            seni = isure * keta
            for j in range(13):
                tmp[(j + seni) % 13 + (kt + 1) * 13] += tmp[kt * 13 + j] % MOD
                # print(nw)

    # print(tmp[(13*kt):13*(kt+1)])
    # tmp = [num % MOD for num in nw]
    # tmp = nw
print(tmp[-8] % MOD)

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
DP=[[0]*13 for _ in range(n+1)]
DP[0][0]=1
for i in range(n):
  r=pow(10,n-1-i,13)
  if s[i]=="?":
    for j in range(10):
      for k in range(13):
        DP[i+1][k]+=DP[i][(k-r*j)%13]
  else:
    for k in range(13):
      DP[i+1][k]+=DP[i][(k-r*int(s[i]))%13]
print(DP[n][5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *

mod = 10**9+7
def rec(k, ti, m):
    if k == N:
        return m == 5
    if memo[k][ti][m] != -1:
        return memo[k][ti][m]
    res = 0
    d = D[N-k-1]
    if S[k] != '?':
        res += rec(k+1, ti, (m+int(S[k])*d)%13)
    else:
        for i in range(10):
            res += rec(k+1, 0, (m+i*d)%13)
    res %= mod
    memo[k][ti][m] = res
    return res

S = input()
N = len(S)
D = [None] * N
t = 1
for i in range(N):
    D[i] = t % 13
    t = t * 10 % 13
memo = [[[-1] * 13 for j in range(2)] for i in range(N+1)]
print(rec(0, 1, 0))

Submission status: Time Limit Exceeded

Solution code:
S = input()
le = len(S)
S = S[::-1]

mod = 10**9 + 7

dp = [0] * (le)
modi = [1] * le
for i in range(le-1):
    modi[i+1] = (modi[i] * 10)%13

dp[0] = ([1]*10 if S[0] == "?" else [int(x == int(S[0])) for x in range(10)]) + [0]*3

for i in range(1,le):
    mo = modi[i]
    a = [0]*13
    b = dp[i-1]
    for j in range(10) if S[i] == "?" else [int(S[i])]:
        for k in range(13):
            a[(k+mo*j)%13] += b[k]
            a[(k+mo*j)%13] %= mod
    dp[i] = a

print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
M = 10 ** 9 + 7
s = input().strip()

num = 0
q_list = []
d = 1
l = len(s)
for i in range(l - 1, -1, -1):
	c = s[i]
	if c != "?":
		num = (num + int(c) * d) % 13
	else:
		q_list.append(d)
	d = (d * 10) % 13

counts = [0] * 13
counts[0] = 1
for d in q_list:
	new_counts = [0] * 13
	for n in range(10):
		r = (d * n) % 13
		for m in range(13):
			k = (r + m) % 13
			new_counts[k] = (new_counts[k] + counts[m]) % M
	counts = new_counts
print(counts[(13 + 5 - num) % 13])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import re
from collections import deque
import sys
import math
input = sys.stdin.readline


def int_raw():
    return int(input())


def ss_raw():
    return input().split()


def ints_raw():
    return tuple(map(int, ss_raw()))


DIV = 10**9+7


def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def ncr(n, r, mod=DIV):
	r = min(r, n-r)
	ret = 1
	for i in range(1, r+1):
		ret = ret * (n-i+1) % mod
		ret = ret * mod_inv(i, mod) % mod
	return ret


def main():
    S = input().rstrip("\n")
    dp = [[0 for i in range(13)] for i in range(len(S)+1)]
    dp [0][0] = 1
    for i in range(1,len(S)+1):
        modi = (10**(i-1)) %13
        s = S[len(S)-i]
        if s!= '?':
            mod_q = (int(s)*modi)%13
            for k in range(13):
                dp[i][(k+mod_q) % 13] = (dp[i][(k+mod_q) % 13]+dp[i-1][k]) % DIV
        else:
            for j in range(10):
                mod_q = (j*modi) % 13
                for k in range(13):
                    dp[i][(k+mod_q) % 13] = (dp[i]
                                             [(k+mod_q) % 13]+dp[i-1][k]) % DIV
    return dp[len(S)][5]
print(main())

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
DP=[[0]*13 for _ in range(n+1)]
DP[0][0]=1
for i in range(n):
  r=pow(10,n-1-i,13)
  if s[i]=="?":
    for j in range(10):
      rr=(r*j)%13
      for k in range(13):
        if k>=rr:
          DP[i+1][k]+=DP[i][k-rr]
        else:
          DP[i+1][k]+=DP[i][k-rr+13]
  else:
    rr=(r*int(s[i]))%13
    for k in range(13):
      if k>=rr:
        DP[i+1][k]+=DP[i][k-rr]
      else:
        DP[i+1][k]+=DP[i][k-rr+13]
print(DP[n][5]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import math
 
s = list(map(str, input().split()))
s = s[0]
n = len(s)

now = 1
amari = []
for i in range(len(s)):
    amari.append(now)
    now = (now * 10) % 13

ans = [[0 for i in range(13)] for j in range(2)]
ans[0][0] = 1
ans[1][0] = 1

for i in range(len(s)):
    now = s[n-1-i]
    ans[(i+1)%2] = [0 for i in range(13)]
    if(now=="?"):
        for k in range(10):
            plus = (amari[i] * k)%13
            for j in range(13):
                ans[(i+1)%2][(j+plus)%13] += ans[i%2][j]
                ans[(i+1)%2][(j+plus)%13] %= 1000000007
    else:
        now = int(now)
        plus = (amari[i] * now)%13
        for j in range(13):
            ans[(i+1)%2][(j+plus)%13] = ans[i%2][j]
            
    last = (i+1)%2
            
print(ans[last][5])

Submission status: Time Limit Exceeded

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

s = input().rstrip()

keta_all = len(s)
amari_cnt_old = [1] + [0] * 12

for i,a in enumerate(s):
	keta_cur = keta_all - i-1
	amari_cnt_new = [0] * 13
	
	if a == "?":
		for j in range(10):
			amari_cur = (j * (10**keta_cur))%13
			for amari_old,amari_cnt_tmp in enumerate(amari_cnt_old):
				amari_cnt_new[(amari_cur+amari_old)%13] += (amari_cnt_tmp%MOD)
	else:
		amari_cur = ((int(a)) * (10**keta_cur))%13
		for amari_old,amari_cnt_tmp in enumerate(amari_cnt_old):
			amari_cnt_new[(amari_cur+amari_old)%13] += (amari_cnt_tmp%MOD)
	
	amari_cnt_old = amari_cnt_new

print((amari_cnt_old[5]%MOD))

Submission status: Time Limit Exceeded

Solution code:
S = input()

MOD = int(1e9+7)
N = len(S)

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

for i in range(N):
  idx = N-i-1
  if i == 0:
    if S[idx] != '?':
      dp[i][int(S[idx])] = 1
    else:
      for j in range(10):
        dp[i][j] = 1
  else:
    amari = (10 ** i) % 13
    if S[idx] != '?':
      shift = int(S[idx]) * amari % 13
      for j in range(13):
        if j+shift < 13:
          dp[i][j+shift] = dp[i-1][j]
        else:
          dp[i][j+shift-13] = dp[i-1][j]
    else:
      for k in range(10):
        shift = k * amari % 13
        for j in range(13):
          if j+shift < 13:
            dp[i][j+shift] = (dp[i][j+shift] + dp[i-1][j]) % MOD
          else:
            dp[i][j+shift-13] = (dp[i][j+shift-13] + dp[i-1][j]) % MOD
            
print(dp[N-1][5])
#print(dp)

Submission status: Time Limit Exceeded

Solution code:
#N=list(map(int, input().split()))
S=input()
big=10**9+7

lis=[0]*13

if S[0]=="?":
	lis=[1]*10+[0]*3
else:
	lis[int(S[0])]=1
S=S[1:]

for i in S:
	newlis=[0]*13
	if i=="?":
		for j in range(10):#はてなの中身
			for k in range(13):#前のあまり
				newlis[(10*k+j)%13]+=lis[k]
	else:
		for k in range(13):
			newlis[(10*k+int(i))%13]+=lis[k]
	lis=newlis.copy()
print(lis[5]%big)

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
DP=[[0]*13 for _ in range(n+1)]
DP[0][0]=1
for i in range(n):
  r=(10**(n-1-i))%13
  if s[i]=="?":
    for j in range(10):
      rr=(r*j)%13
      for k in range(13):
        if k>=rr:
          DP[i+1][k]+=DP[i][k-rr]
        else:
          DP[i+1][k]+=DP[i][k-rr+13]
  else:
    rr=(r*int(s[i]))%13
    for k in range(13):
      if k>=rr:
        DP[i+1][k]+=DP[i][k-rr]
      else:
        DP[i+1][k]+=DP[i][k-rr+13]
print(DP[n][5]%(10**9+7))

Submission status: Time Limit Exceeded

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

PRIME = 10 ** 9 + 7


def digitmod13(k, n):
    return (k * (10 ** n)) % 13


def main():
    S = input()
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(N)]
    S = S[::-1]
    # init
    first = S[0]
    if first == '?':
        for k in range(10):
            dp[0][k] = 1
    else:
        first = int(first)
        dp[0][first] = 1
    for i in range(1, N):
        c = S[i]
        if c == '?':
            for d in range(13):
                for k in range(10):
                    dp[i][(d + digitmod13(k, i)) % 13] += dp[i - 1][d]
        else:
            c = int(c)
            for d in range(13):
                dp[i][(d + digitmod13(c, i)) % 13] += dp[i - 1][d]
        for d in range(13):
            dp[i][d] %= PRIME
    
    print(dp[N - 1][5] % PRIME)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7

S = input()
N = len(S)
amari = [0 for _ in range(13)]


for i, s in enumerate(S):
    if i == 0:
        next_amari = [0 for _ in range(13)]
        if s != "?":
            number = int(s)
            now_amari = number * pow(10, N-1-i, 13) % 13
            next_amari[now_amari] = 1
        else:
            for number in range(10):
                now_amari = number * pow(10, N-1-i, 13) % 13
                next_amari[now_amari] += 1
        amari = next_amari
        continue

    next_amari = [0 for _ in range(13)]
    if s != "?":
        number = int(s)
        now_amari = number * pow(10, N-1-i, 13) % 13
        for j, n in enumerate(amari):
            next_amari[(j+now_amari) % 13] = n
    else:
        for number in range(10):
            now_amari = number * pow(10, N-1-i, 13) % 13
            for j, n in enumerate(amari):
                next_amari[(j+now_amari) % 13] = (n+next_amari[(j+now_amari) % 13])%MOD

    amari = next_amari
print(amari[5])

Submission status: Time Limit Exceeded

Solution code:

S = input()

s = list(S)

s.reverse()

#print (s)

lis = [0] * 13
lis[0] = 1

for i in range(len(S)):

    nlis = [0] * 13

    if s[i] == "?":

        for j in range(10):

            for k in range(13):

                nlis[ (k + (j * (10**i))) % 13] += lis[k]

    else:

        now = int(s[i])

        for k in range(13):

            nlis[ (k + (now * (10 ** i))) % 13 ] += lis[k]

    #print (nlis)
    lis = nlis.copy()

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

Submission status: Time Limit Exceeded

Solution code:
s = list(str(input()))
n = len(s)

from itertools import product

ans = 0

m = s.count('?')

for x in product([0,1,2,3,4,5,6,7,8,9], repeat=m):
    p_x = 0
    s_num = 0
    for i in range(n):
        if s[i] == '?':
            s_num += int(x[p_x])*(10**(n-1-i))
            p_x += 1
        else:
            s_num += int(s[i])*(10**(n-1-i))
    if s_num % 13 == 5:
        ans += 1

print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
s = raw_input()
mod = 10 ** 9 + 7
d = [0 for _ in xrange(13)]
base = 1
d[0] = 1
for c in s[::-1]:
    d2 = [0 for _ in xrange(13)]
    if c == '?':
        for x in xrange(10):
            for y in xrange(13):
                t = (x * base + y) % 13
                d2[t] = (d2[t] + d[y]) % mod
    else:
        x = int(c)
        for y in xrange(13):
            t = (x * base + y) % 13
            d2[t] = (d2[t] + d[y]) % mod
    for i in xrange(13):
        d[i] = d2[i] % mod
    base = base * 10 % 13
print d[5]

Submission status: Time Limit Exceeded

Solution code:
S=str(input())
num=len(S)
target=0
mod=1000000007
dp=[0,0,0,0,0,0,0,0,0,0,0,0,0]
dp2=[0,0,0,0,0,0,0,0,0,0,0,0,0]
if(S[0]=="?"):
    for i in range(0,10):
        dp[i]=1
else:
    dp[int(S[0])]=1
for i in range(1,num):
    target=S[i]
    if(target=="?"):
        for j in range(0,13):
            for k in range(0,10):
                dp2[(j*10+k)%13]+=dp[j]
    else:
        target=int(target)
        for j in range(0,13):
            dp2[(j*10+target)%13]+=dp[j]
    for j in range(0,13):
        dp[j]=dp2[j]%mod
        dp2[j]=0
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from collections import deque
import itertools
from itertools import permutations
import sys
import bisect
sys.setrecursionlimit(10**6)
#input=sys.stdin.readline
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
YNeos='YNeos'
mo=10**9+7
imp='IMPOSSIBLE'


s=input()
t=list(s)[::-1]
ans=0
dp=[0]*13
dp[0]=1
for d in range(len(t)):
    
    if t[d]=='?':
        tm=[0]*13
        for x in range(10):
            r=int(x)*(10**d)
            for i in range(13):
                tm[(i+r)%13]+=dp[i]
        dp=[j%mo for j in tm]
    else:
        tm=[0]*13
        r=int(t[d])*(10**d)
        for i in range(13):
            tm[(i+r)%13]=dp[i]
        dp=[j for j in tm]
    #print(dp)

print(dp[5]%mo)

Submission status: Time Limit Exceeded

Solution code:
import sys


fin = sys.stdin.readline
MOD = 10 ** 9 + 7
S = fin().rstrip("\n")[::-1]
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
for i, c in enumerate(S, start=1):
    base = 10 ** (i - 1) % 13
    if c != '?':
        d = int(c) * base % 13
        for r in range(13):
            c = (d + r) % 13
            dp[i][c] += dp[i - 1][r]
            dp[i][c] %= MOD
    else:
        for d in range(10):
            d = d * base % 13
            for r in range(13):
                c = (d + r) % 13
                dp[i][c] += dp[i - 1][r]
                dp[i][c] %= MOD
print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
def NextAmari(prev,d):
    return((prev*10+d)%13)

S = input()
mod = 10**9 + 7
DP = [[0]*13 for i in range(len(S)+1)]#DP[i][j] = 上位i桁目まで見たときの、j(mod13)の数　0<=j<13

DP[0][0] = 1
for n,s in enumerate(S):
    i = n
    if s != "?":
        d = int(s)
        for j,num in enumerate(DP[i]):
            DP[i+1][NextAmari(j,d)] += num
    else:
        for d in range(10):
            for j,num in enumerate(DP[i]):
                DP[i+1][NextAmari(j,d)] += num
    for a in range(13):
        DP[i+1][a] %= mod
print(DP[-1][5])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# coding: utf-8

""" """

import argparse


def parse_arguments():
    parser = argparse.ArgumentParser(description=' ')
    parser.add_argument('-i', '--input_file', required=True)
    parser.add_argument('-o', '--output_file', required=True)
    args = parser.parse_args()
    return args

MOD = 10**9+7
def main():
    s = input()
    dp = [[0 for _ in range(13)] for _ in range(len(s)+1)]
    dp[0][0] = 1
    lm = dict()
    for d in range(10):
        for m in range(13):
            lm[(m,d)] = (10*m+d)%13
    for i in range(len(s)):
        c = s[i]
        if c != '?':
            d = int(c)
            for m in range(13):
                dp[i+1][lm[(m,d)]] += dp[i][m]
        else:
            for d in range(10):
                for m in range(13):
                    dp[i+1][lm[(m,d)]] += dp[i][m]
        if i & 1:
            for m in range(13):
                dp[i+1][m] %= MOD
    print(dp[len(s)][5] % MOD)


if __name__ == '__main__':
    # args = parse_arguments()
    main()

Submission status: Time Limit Exceeded

Solution code:
M = 10 ** 9 + 7
s = input().strip()

num = 0
q_list = []
d = 1
l = len(s)
for i in range(l - 1, -1, -1):
	c = s[i]
	if c != "?":
		num = (num + int(c) * d) % 13
	else:
		q_list.append(d)
	d *= 10

counts = [0] * 13
counts[0] = 1
for d in q_list:
	new_counts = [0] * 13
	for n in range(10):
		r = (d * n) % 13
		for m in range(13):
			k = (r + m) % 13
			new_counts[k] = (new_counts[k] + counts[m]) % M
	counts = new_counts

print(counts[(13 + 5 - num) % 13])

Submission status: Time Limit Exceeded

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

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

for i in range(1, len(s)):
    for j in range(13):
        dp[i%2][j] = 0

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

    # print(dp[(i-1)%2])
    # print(dp[i%2])
    # print()


print(dp[(len(s)-1)%2][5])