Problem:


Score : 400 points

Problem Statement

Given is a string S. Each character in S is either a digit (0, ..., 9) or ?.

Among the integers obtained by replacing each occurrence of ? with a digit, how many have a remainder of 5 when divided by 13? An integer may begin with 0.

Since the answer can be enormous, print the count modulo 10^9+7.

Constraints

S is a string consisting of digits (0, ..., 9) and ?.

1 \leq |S| \leq 10^5

Input

Input is given from Standard Input in the following format:

S

Output

Print the number of integers satisfying the condition, modulo 10^9+7.

Sample Input 1

??2??5

Sample Output 1

768

For example, 482305, 002865, and 972665 satisfy the condition.

Sample Input 2

?44

Sample Output 2

1

Only 044 satisfies the condition.

Sample Input 3

7?4

Sample Output 3

0

We may not be able to produce an integer satisfying the condition.

Sample Input 4

?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76???

Sample Output 4

153716888



Sample input:
??2??5


Sample output:
768

Submission status: Time Limit Exceeded

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
S = sr()
# 桁DP, 上から
dp = [0] * 13
dp[0] = 1
for s in S:
    prev = [x for x in dp]
    dp = [0] * 13
    if s == '?':
        loop = range(10)
    else:
        loop = [int(s)]
    for j in range(13):
        for lo in loop:
            dp[(10*j+lo)%13] += prev[j]
    dp = [x%MOD for x in dp]

answer = dp[5]
print(answer%MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
S = sr()
# 桁DP, 上から
dp = [0] * 13
dp[0] = 1
for s in S:
    prev = [x for x in dp]
    num = s
    dp = [0] * 13
    if num != '?':
        num = int(num)
        for j in range(13):
            dp[(10*j+num)%13] = prev[j]
    else:
        for j in range(13):
            for k in range(10):
                dp[(10*j+k)%13] += prev[j]
            dp[j] %= MOD

answer = dp[5]
print(answer%MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
S = sr()
# 桁DP, 上から
dp = [0] * 13
dp[0] = 1
for i in range(len(S)):
    prev = [x for x in dp]
    num = S[i]
    dp = [0] * 13
    if num != '?':
        num = int(num)
        for j in range(13):
            dp[(10*j+num)%13] = prev[j]
    else:
        for j in range(13):
            for k in range(10):
                dp[(10*j+k)%13] += prev[j]
            dp[j] %= MOD

answer = dp[5]
print(answer%MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def main():
    MOD = 10 ** 9 + 7
    S = sr()
    # 桁DP, 上から
    dp = [[0] * 13 for _ in range(2)]
    dp[0][0] = 1
    for i in range(len(S)):
        num = S[i]
        i %= 2
        if num.isdigit():
            num = int(num)
            for j in range(13):
                dp[1-i][(10*j+num)%13] = dp[i][j]
        else:
            dp[1-i] = [0] * 13
            for j in range(13):
                for k in range(10):
                    dp[1-i][(10*j+k)%13] += dp[i][j]
                dp[1-i][j] %= MOD

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
S = sr()
# 桁DP, 上から
dp = [[0] * 13 for _ in range(2)]
dp[0][0] = 1
for i in range(len(S)):
    #prev = dp.copy()
    num = S[i]
    i %= 2
    #dp = [0] * 13
    if num.isdigit():
        num = int(num)
        for j in range(13):
            dp[1-i][(10*j+num)%13] = dp[i][j]
    else:
        dp[1-i] = [0] * 13
        for j in range(13):
            for k in range(10):
                dp[1-i][(10*j+k)%13] += dp[i][j]
            dp[1-i][j] %= MOD

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
S = sr()
# 桁DP, 上から
dp = [0] * 13
dp[0] = 1
for i in range(len(S)):
    prev = dp.copy()
    num = S[i]
    dp = [0] * 13
    if num.isdigit():
        num = int(num)
        for j in range(13):
            dp[(10*j+num)%13] = prev[j]
    else:
        for j in range(13):
            for k in range(10):
                dp[(10*j+k)%13] += prev[j]
            dp[j] %= MOD

answer = dp[5]
print(answer%MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappush, heappop
#input = sys.stdin.readline

def main():
    s=list(input())
    n=len(s)
    mod=10**9+7
    dp=[[0]*13 for _ 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):
        for j in range(13):
            if s[i]=='?':
                for k in range(10):
                    x=(j*10+k)%13
                    dp[i][x]+=dp[i-1][j]
                    dp[i][x]%=mod
            else:
                x=(j*10+int(s[i]))%13
                dp[i][x]+=dp[i-1][j]
                dp[i][x]%=mod
    print(dp[n-1][5])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 反転させて扱いやすくしておく S[i]は10^iの個数を表すようになる
S = input()[::-1]

MOD = 10 ** 9 + 7
class modint:
    def __init__(self, x):
        self.x = x.x if isinstance(x, modint) else x % MOD
    def __str__(self): return str(self.x)
    __repr__ = __str__
    def __int__(self): return self.x
    __index__ = __int__
    def __add__(self, other): return modint(self.x + modint(other).x)
    def __sub__(self, other): return modint(self.x - modint(other).x)
    def __mul__(self, other): return modint(self.x * modint(other).x)
    def __pow__(self, other): return modint(pow(self.x, modint(other).x, MOD))
    def __floordiv__(self, other): return modint(self.x * pow(modint(other).x, MOD - 2, MOD))
    def __eq__(self, other): return self.x == modint(other).x
    def __ne__(self, other): return self.x != modint(other).x
    def __inv__(self): return pow(self.x, MOD - 2, MOD)

# 10^i%13を求める
def mod13_of_10pow(i):
    return [1, 10, 9, 12, 3, 4][i % 6]


# ans[k] : 13で割った余りがkになる数の個数
# 最後のans[5]が答えになる
ans = [modint(0)] * 13

for i, c in enumerate(S):
    if i == 0:
        if c != '?':
            ans[int(c)] += 1
        else:
            for q in range(10):
                ans[q] += 1
        continue

    tmp = [modint(0)] * 13

    m = mod13_of_10pow(i)
    ds = [int(c)] if c != '?' else [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    for d in ds:
        for k in range(13):
            tmp[(k + d * m) % 13] += ans[k]

    ans = tmp

print(ans[5])

Submission status: Time Limit Exceeded

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

main()

Submission status: Time Limit Exceeded

Solution code:
def main():

    S = input() # input
    mod = pow(10,9) + 7 # divisor

    # 動的計画法で解く
    dp = [[0 for _ in range(13)] for _ in range(len(S)+1)] 
    dp[0][0] = 1
    mul = 1

    for i in range(1,len(S)+1):

        # i桁目が?でない場合
        if S[-i] != '?':
            for j in range(13):
                dp[i][(int(S[-i])*mul + j) % 13] += dp[i-1][j]%mod

        # i桁目が?だった場合
        else:
            for j in range(13):
                for k in range(10):
                    dp[i][(k*mul + j) % 13] += dp[i-1][j]%mod

        mul = (mul*10)%13

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

main()

Submission status: Time Limit Exceeded

Solution code:
def main():

    S = input() # input
    mod = pow(10,9) + 7 # divisor

    # 動的計画法で解く
    dp = [[0 for _ in range(13)] for _ in range(len(S)+1)] 
    dp[0][0] = 1
    mul = 1

    for i in range(1,len(S)+1):

        # i桁目が?でない場合
        if S[-i] != '?':
            for j in range(13):
                dp[i][(int(S[-i])*mul + j) % 13] += dp[i-1][j]

        # i桁目が?だった場合
        else:
            for j in range(13):
                for k in range(10):
                    dp[i][(k*mul + j) % 13] += dp[i-1][j]

        mul *= 10
        mul %= 13

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

main()

Submission status: Time Limit Exceeded

Solution code:
def main():

    S = input() # input
    mod = pow(10,9) + 7 # divisor

    # 動的計画法で解く
    dp = [[0 for _ in range(13)] for _ in range(len(S)+1)] 
    dp[0][0] = 1
    mul = 1

    for i in range(1,len(S)+1):

        # i桁目が?でない場合
        if S[-i] != '?':
            for j in range(13):
                dp[i][(int(S[-i])*mul + j) % 13] += dp[i-1][j]%mod

        # i桁目が?だった場合
        else:
            for j in range(13):
                for k in range(10):
                    dp[i][(k*mul + j) % 13] += dp[i-1][j]%mod

        mul *= 10
        mul %= 13

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

main()

Submission status: Time Limit Exceeded

Solution code:
def main():

    S = input() # input
    mod = pow(10,9) + 7 # divisor

    # 動的計画法で解く
    dp = [[0 for _ in range(13)] for _ in range(len(S)+1)] 
    dp[0][0] = 1

    for i in range(1,len(S)+1):

        # i桁目が?でない場合
        if S[-i] != '?':
            for j in range(13):
                dp[i][(int(S[-i])*pow(10,i-1) + j) % 13] += dp[i-1][j]%mod

        # i桁目が?だった場合
        else:
            for j in range(13):
                for k in range(10):
                    dp[i][(k*pow(10,i-1) + j) % 13] += dp[i-1][j]%mod

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

main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
S = list(S)
S.reverse()

dp = [[0]*13 for _ in range(N + 1)]
dp[0][0] = 1
mod = 10**9+7
pow10 = 1
for i in range(1, N + 1):
    if S[i-1] == "?":
        for j in range(13):
            for k in range(10):
                dp[i][(j + k*pow10) % 13] += dp[i-1][j]
    else:
        for j in range(13):
            dp[i][(j+int(S[i-1])*pow10) % 13] = dp[i-1][j]
    pow10 *= 10
    for j in range(13):
        dp[i][j] %= mod

print(dp[N][5])

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
S = list(S)
S.reverse()

dp = [[0]*13 for _ in range(100100)]
dp[0][0] = 1
mod = 10**9+7
for i in range(1, N + 1):
    if S[i-1] == "?":
        for j in range(13):
            for k in range(10):
                dp[i][(j + k*10**(i-1)) % 13] += dp[i-1][j]
    else:
        for j in range(13):
            dp[i][(j+int(S[i-1])*10**(i-1)) % 13] = dp[i-1][j]

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

print(dp[N][5])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
D - Digits Parade
https://atcoder.jp/contests/abc135/tasks/abc135_d

"""
import sys


def solve(S):
    dp = [[0] * 13 for _ in range(len(S)+1)]
    dp[0][0] = 1
    for i, ch in enumerate(S):
        c = -1 if ch == '?' else int(ch)
        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] %= (10**9 + 7)
    return dp[len(S)][5]


def main(args):
    S = input()
    ans = solve(S)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
S = list(input())

MOD = 10 ** 9 + 7

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

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

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

Submission status: Time Limit Exceeded

Solution code:
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd
import sys
#input = sys.stdin.readline

import copy
"""
from collections import *
S=input()
dp=[[0 for i in range(13)] for m 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 in range(1,len(S)):
    for m in range(13):
        if S[i]=="?":
            for j in range(10):
                dp[i][(m*10+j)%13]+=dp[i-1][m]
        else:
            dp[i][(m*10+int(S[i]))%13]+=dp[i-1][m]
#print(dp)
print(dp[-1][5]%mod)

Submission status: Time Limit Exceeded

Solution code:
def main():
    
    s = input()[::-1]
    mod = 10**9+7
    dp = [[0 for j in range(13)] for i in range(len(s)+1)]
    dp[0][0] = 1
    ten = 1


    for i in range(len(s)):
        if s[i] == "?":
            for k in range(10):
                x = k*ten%13
                for j in range(13):
                    dp[i+1][(j+x)%13] = (dp[i][j]+dp[i+1][(j+x)%13])%mod
        
        else:
            x = int(s[i])*ten%13
            for j in range(13):
                dp[i+1][(j+x)%13] += dp[i][j]%mod

        ten *= 10%mod

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


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

        ten *= 10%mod

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

    ten *= 10%mod

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

S = input()
N = len(S)

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

rem = [[0 for k in range(10)] for j in range(13)]

for j in range(13):
    for k in range(10):
        rem[j][k] = (10 * j + k) % 13

for i in range(N):
    for j in range(13):
        if S[i] == '?':
            for k in range(10):
                dp[i + 1][rem[j][k]] += dp[i][j]
                dp[i + 1][rem[j][k]] %= MOD
        else:
            k = int(S[i])
            dp[i + 1][rem[j][k]] += dp[i][j]
            dp[i + 1][rem[j][k]] %= MOD

print(dp[N][5])

Submission status: Time Limit Exceeded

Solution code:
S = input()
S = S[::-1]
N = len(S)
mod = 10 ** 9 + 7

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

for i, s in enumerate(S):
    if s == "?":
        val = tuple(range(10))
    else:
        val = (int(s),)

    digit = pow(10, i, 13)
    for j in range(13):
        for k in val:
            ni = i + 1
            nj = (j + digit * k) % 13
            dp[ni][nj] += dp[i][j]
            dp[ni][nj] %= mod

ans = dp[N][5] % mod
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:


s = str(input())
n = len(s)
mod = (10**9)+7

DP = [[0 for _ in range(13)] for _ in range(n)]

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

# 下2桁目から順に見ていく
baisu = 1
for i in range(1,n):
    num_s = s[n-(i+1)]
    baisu *= 10
    if num_s != '?':
        now = int(num_s) * baisu
        res = now % 13
        # 元の余りj -> (res+j)%13 が今回の余り 
        for j in range(13):
            nex = (j+res)%13
            DP[i][nex] = (DP[i-1][j] + DP[i][nex]) % mod
            
    else:
        for k in range(10):
            now = k * baisu
            res = now % 13
            # 元の余りj -> (res+j)%13 が今回の余り
            for j in range(13):
                nex = (j+res)%13
                DP[i][nex] = (DP[i-1][j] + DP[i][nex]) % mod

ans = DP[n-1][5]
print(ans)

Submission status: Time Limit Exceeded

Solution code:


s = str(input())
n = len(s)
mod = (10**9)+7

DP = [[0 for _ in range(13)] for _ in range(n)]

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

# 下2桁目から順に見ていく
for i in range(1,n):
    num_s = s[n-(i+1)]
    baisu = 10 ** i
    if num_s != '?':
        now = int(num_s) * baisu
        res = now % 13
        # 元の余りj -> (res+j)%13 が今回の余り 
        for j in range(13):
            nex = (j+res)%13
            DP[i][nex] = (DP[i-1][j] + DP[i][nex]) % mod
            
    else:
        for k in range(10):
            now = k * baisu
            res = now % 13
            # 元の余りj -> (res+j)%13 が今回の余り
            for j in range(13):
                nex = (j+res)%13
                DP[i][nex] = (DP[i-1][j] + DP[i][nex]) % mod
                
ans = DP[n-1][5]
print(ans)

Submission status: Time Limit Exceeded

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

DP = [[0 for _ in range(13)] for _ in range(2)]

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

# 下2桁目から順に見ていく
for i in range(1,n):
    # DPの1行目に入れるようにする
    for l in range(13):
        DP[0][l] = DP[1][l]
        DP[1][l] = 0

    num_s = s[n-(i+1)]
    baisu = 10 ** i
    if num_s != '?':
        now = int(num_s) * baisu
        res = now % 13
        # 元の余りj -> (res+j)%13 が今回の余り 
        for j in range(13):
            nex = (j+res)%13
            DP[1][nex] += DP[0][j]
            DP[1][nex] %= mod
    else:
        for k in range(10):
            now = k * baisu
            res = now % 13
            # 元の余りj -> (res+j)%13 が今回の余り
            for j in range(13):
                nex = (j+res)%13
                DP[1][nex] += DP[0][j]
                DP[1][nex] %= mod

ans = DP[1][5]
print(ans)        


# s = str(input())
# n = len(s)
# mod = (10**9)+7

# DP = [[0 for _ in range(13)] for _ in range(n)]

# if s[-1] == '?':
#     for i in range(0,10):
#         DP[0][i] += 1
# else:
#     DP[0][int(s[-1])] = 1

# # 下2桁目から順に見ていく
# for i in range(1,n):
#     num_s = s[n-(i+1)]
#     baisu = 10 ** i
#     if num_s != '?':
#         now = int(num_s) * baisu
#         res = now % 13
#         # 元の余りj -> (res+j)%13 が今回の余り 
#         for j in range(13):
#             nex = (j+res)%13
#             DP[i][nex] += DP[i-1][j]
#             DP[i][nex] %= mod
#     else:
#         for k in range(10):
#             now = k * baisu
#             res = now % 13
#             # 元の余りj -> (res+j)%13 が今回の余り
#             for j in range(13):
#                 nex = (j+res)%13
#                 DP[i][nex] += DP[i-1][j]
#                 DP[i][nex] %= mod

# ans = DP[n-1][5]
# print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s = str(input())
n = len(s)
mod = (10**9)+7

DP = np.array([[0 for _ in range(13)] for _ in range(n)])

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

# 下2桁目から順に見ていく
for i in range(1,n):
    num_s = s[n-(i+1)]
    baisu = 10 ** i
    if num_s != '?':
        now = int(num_s) * baisu
        res = now % 13
        # 元の余りj -> (res+j)%13 が今回の余り 
        for j in range(13):
            nex = (j+res)%13
            DP[i][nex] += DP[i-1][j]
            DP[i][nex] %= mod
    else:
        for k in range(10):
            now = k * baisu
            res = now % 13
            # 元の余りj -> (res+j)%13 が今回の余り
            for j in range(13):
                nex = (j+res)%13
                DP[i][nex] += DP[i-1][j]
                DP[i][nex] %= mod

ans = DP[n-1][5]
print(ans)

Submission status: Time Limit Exceeded

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

DP = [[0 for _ in range(13)] for _ in range(n)]

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

# 下2桁目から順に見ていく
for i in range(1,n):
    num_s = s[n-(i+1)]
    baisu = 10 ** i
    if num_s != '?':
        now = int(num_s) * baisu
        res = now % 13
        # 元の余りj -> (res+j)%13 が今回の余り 
        for j in range(13):
            DP[i][(j+res)%13] += DP[i-1][j]
            DP[i][(j+res)%13] %= mod
    else:
        for k in range(10):
            now = k * baisu
            res = now % 13
            # 元の余りj -> (res+j)%13 が今回の余り
            for j in range(13):
                DP[i][(j+res)%13] += DP[i-1][j]
                DP[i][(j+res)%13] %= mod

ans = DP[n-1][5]
print(ans)

Submission status: Time Limit Exceeded

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

DP = [[0 for _ in range(13)] for _ in range(n)]

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

# 下2桁目から順に見ていく
for i in range(1,n):
    num_s = s[n-(i+1)]
    if num_s != '?':
        num = int(num_s)
        now = num * (10**i)
        res = now % 13
        # 元の余りj -> (res+j)%13 が今回の余り 
        for j in range(13):
            DP[i][(j+res)%13] += DP[i-1][j]
            # DP[i][(j+res)%13] %= mod
    else:
        for k in range(10):
            now = k * (10**i)
            res = now % 13
            # 元の余りj -> (res+j)%13 が今回の余り
            for j in range(13):
                DP[i][(j+res)%13] += DP[i-1][j]
                # DP[i][(j+res)%13] %= mod

ans = DP[n-1][5] % mod
print(ans)

Submission status: Time Limit Exceeded

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

DP = [[0 for _ in range(13)] for _ in range(n)]

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

# 下2桁目から順に見ていく
for i in range(1,n):
    num_s = s[n-(i+1)]
    if num_s != '?':
        num = int(num_s)
        now = num * (10**i)
        res = now % 13
        # 元の余りj -> (res+j)%13 が今回の余り 
        for j in range(13):
            DP[i][(j+res)%13] += DP[i-1][j]
            DP[i][(j+res)%13] %= mod
    else:
        for k in range(10):
            now = k * (10**i)
            res = now % 13
            # 元の余りj -> (res+j)%13 が今回の余り
            for j in range(13):
                DP[i][(j+res)%13] += DP[i-1][j]
                DP[i][(j+res)%13] %= mod

ans = DP[n-1][5]
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def STR(): return input()

mod = 1000000007

s = STR()
l = len(s)
dp = [[0] * 13 for _ in range(l + 1)] #dp[i]i桁目まで決めた時の13で割ったあまりが[j]の個数
dp[0][0] = 1

for i in range(l + 1): #i桁目まで決める
    if s[i-1] == '?':
        for j in range(13): #i-1桁目のあまりがj
            a = dp[i-1][j]
            b = j * 10
            for k in range(10): #i桁目の値
                dp[i][(b + k) % 13] += a
        for j in range(13):
            dp[i][j] %= mod
    else:
        a = int(s[i-1])
        for j in range(13): #i-1桁目のあまりがj
            num = (j * 10 + a) % 13
            dp[i][num] += dp[i-1][j]
            dp[i][num] %= mod
#print(dp)
print(dp[l][5])

Submission status: Time Limit Exceeded

Solution code:
def STR(): return '?' * pow(10, 5)#input()

mod = 1000000007

s = STR()
l = len(s)
dp = [[0] * 13 for _ in range(l + 1)] #dp[i]i桁目まで決めた時の13で割ったあまりが[j]の個数
dp[0][0] = 1

for i in range(l + 1): #i桁目まで決める
    if s[i-1] == '?':
        for j in range(13): #i-1桁目のあまりがj
            a = dp[i-1][j]
            b = j * 10
            for k in range(10): #i桁目の値
                dp[i][(b + k) % 13] += a
        for j in range(13):
            dp[i][j] %= mod
    else:
        a = int(s[i-1])
        for j in range(13): #i-1桁目のあまりがj
            num = (j * 10 + a) % 13
            dp[i][num] += dp[i-1][j]
            dp[i][num] %= mod
#print(dp)
print(dp[l][5])

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
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 STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

s = STR()
l = len(s)

dp = [[0 for _ in range(13)] for _ in range(l)] #dp[i]i桁目まで決めた時の13で割ったあまりが[j]の個数
if s[0] == '?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(s[0])] = 1

for i in range(1, l): #i桁目まで決める
    for j in range(13): #i-1桁目のあまりがj
        if s[i] != '?':
            num = (j * 10 + int(s[i])) % 13
            dp[i][num] += dp[i-1][j]
            dp[i][num] %= mod
        else:
            for k in range(10): #i桁目の値
                num = (j * 10 + k) % 13
                dp[i][num] += dp[i-1][j]
                dp[i][num] %= mod
#print(dp)
print(dp[l-1][5])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
s=input()
dp=[[0]*13 for _ in range(len(s)+5)]
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):
        if c!=-1 and c!=j:
            continue
        for k in range(13):
            dp[i+1][(k*10+j)%13]+=dp[i][k]
            dp[i+1][(k*10+j)%13]%=(10**9+7)


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

Submission status: Time Limit Exceeded

Solution code:
s=input()
dp=[[0]*13 for _ in range(len(s)+5)]
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):
        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]%=(10**9+7)

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

Submission status: Time Limit Exceeded

Solution code:
s=input()
dp=[[0]*13 for _ in range(10**5+5)]
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):
        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]%=(10**9+7)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines 
MOD = 10**9+7

S = inpS()
N = len(S)
dp = [0]*13

dp[0] = 1
mul = 1
for i in range(N-1, -1, -1):
  nextDP = [0]*13
  s = S[i]
  if s == "?":
    for dgt in range(10):
      for mo in range(13):
        ind = (dgt*mul+mo)%13
        nextDP[ind] += dp[mo]
        nextDP[ind] %= MOD        
  else:
    dgt = int(S[i])
    for mo in range(13):
      ind = (dgt*mul+mo)%13
      nextDP[ind] += dp[mo]
      nextDP[ind] %= MOD    
  mul *= 10
  mul %= 13
  dp = nextDP
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def modinv(a, m):
    g, x, y = xgcd(a, m)
    return x % m
def main():
    s=list(input())
    mod=10**9+7
    K=modinv(10,13)
    U=[[0 for i in range(10) ]for k in range(13)]
    for i in range(13):
        for j in range(10):
            U[i][j]=((i-j)*K)%13

    dp=[[0 for k in range(13)] for i in range(len(s))]
    #dp[i][j]=初めのindex=i番目まで見たときに、あまりがjになるような方法の総数
    num=s[0]
    if s[0]=="?":
        for i in range(10):
            dp[0][i]=1
    else:
        number=int(s[0])
        dp[0][number]=1

    for i in range(1,len(s)):
        if s[i]=="?":
            for k in range(13):
                for j in range(10):
                    dp[i][k]+=dp[i-1][U[k][j]]%mod
            continue
        else:
            number=int(s[i])
            for k in range(13):
                dp[i][k]=dp[i-1][U[k][number]]
    print(dp[len(s)-1][5]%mod)
if __name__ == "__main__":
    main()