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:
def main():
    s = list(reversed(input()))
    mod = 10**9+7
    memo = [0 for _ in [0]*13]
    m13 = [(10**i) % 13 for i in range(12)]
    memo[0] = 1
    for i in range(len(s)):
        memo2 = [0 for _ in [0]*13]
        a = m13[i % 12]
        if s[i] == "?":
            for l in [(a*j) % 13 for j in range(10)]:
                for j in range(13):
                    memo2[(l+j) % 13] += memo[j]
        else:
            l = a*int(s[i])
            memo2 = memo[(-l) % 13:]+memo[:(-l) % 13]
        memo = [j % mod for j in memo2]
    print(memo[5])


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = list(reversed(input()))
    mod = 10**9+7
    memo = [0 for _ in [0]*13]
    m13 = [(10**i) % 13 for i in range(12)]
    memo[0] = 1
    for i in range(len(s)):
        memo2 = [0 for _ in [0]*13]
        a = m13[i % 12]
        if s[i] == "?":
            list_ = [(a*j) % 13 for j in range(10)]
            for l in list_:
                for j in range(13):
                    memo2[(l+j) % 13] += memo[j]
        else:
            l = a*int(s[i])
            for j in range(13):
                memo2[(l+j) % 13] += memo[j]
        memo = [j % mod for j in memo2]
    print(memo[5])


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import numpy as np
    s = list(reversed(input()))
    mod = 10**9+7
    memo = np.zeros(13, dtype=np.int64)
    m13 = [(10**i) % 13 for i in range(12)]
    npa13 = np.array([i * np.arange(10) % 13 for i in range(13)])
    memo[0] = 1
    for j, i in enumerate(s):
        memo2 = np.zeros(13, dtype=np.int64)
        a = m13[j % 12]
        if i == "?":
            for l in npa13[a]:
                memo2[l:] += memo[:13-l]
                memo2[:l] += memo[13-l:]
            memo = memo2 % mod
        else:
            l = a*int(i) % 13
            memo = np.append(memo[13-l:], memo[:13-l]) % mod
    print(int(memo[5]))


main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
q = s.count("?")
# 先頭i文字で数えられるもののうちあまりがjであるものの数
dp = [[0 for _ in range(13)] for _ in range(len(s))]

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    import numpy as np
    s = list(reversed(input()))
    mod = 10**9+7
    memo = np.zeros(13, dtype=np.int64)
    m13 = [(10**i) % 13 for i in range(12)]
    memo[0] = 1
    for j, i in enumerate(s):
        memo2 = np.zeros(13, dtype=np.int64)
        a = m13[j % 12]
        if i == "?":
            for l in a*np.arange(10) % 13:
                memo2[l:] += memo[:13-l]
                memo2[:l] += memo[13-l:]
            memo = memo2 % mod
        else:
            l = a*int(i) % 13
            memo2[l:] += memo[:13-l]
            memo2[:l] += memo[13-l:]
            memo = memo2 % mod
    print(int(memo[5]))


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import numpy as np
    s = list(reversed(input()))
    mod = 10**9+7
    memo = np.zeros(13, dtype=np.int64)
    m13 = [(10**i) % 13 for i in range(12)]
    memo[0] = 1
    for i in range(len(s)):
        memo2 = np.zeros(13, dtype=np.int64)
        a = m13[i % 12]
        if s[i] == "?":
            for l in a*np.arange(10) % 13:
                memo2[l:] += memo[:13-l]
                memo2[:l] += memo[13-l:]
            memo = memo2 % mod
        else:
            l = a*int(s[i]) % 13
            memo2[l:] += memo[:13-l]
            memo2[:l] += memo[13-l:]
            memo = memo2 % mod
    print(int(memo[5]))


main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
q = s.count("?")
# 先頭i文字で数えられるもののうちあまりがjであるものの数
dp = [[0 for _ in range(13)] for _ in range(len(s))]

for i, v in enumerate(s):
    if i == 0:
        if v == '?':
            for j in range(10):
                dp[0][j] += 1
        else:
            dp[0][int(v)] += 1
    else:
        if v == '?':
            for j in range(13):
                if dp[i-1][j] > 0:
                    for k in range(10):
                        dp[i][(10 * j + k) % 13] += dp[i-1][j]
                dp[i][j] = dp[i][j] % 1000000007
        else:
            for j in range(13):
                if dp[i-1][j] > 0:
                    dp[i][(10 * j + int(v)) % 13] += dp[i - 1][j]
                dp[i][j] = dp[i][j] % 1000000007

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    import numpy as np
    s = list(reversed(input()))
    mod = 10**9+7
    memo = np.zeros(13)
    m13 = [(10**i) % 13 for i in range(12)]
    memo[0] = 1
    for i in range(len(s)):
        memo2 = np.zeros(13)
        a = m13[i % 12]
        if s[i] == "?":
            list_ = np.arange(10)
        else:
            list_ = np.array([int(s[i])])
        list_ = a*list_ % 13
        for l in list_:
            memo2[l:] += memo[:13-l]
            memo2[:l] += memo[13-l:]
        memo = memo2 % mod
    print(int(memo[5]))


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import numpy as np
    s = list(reversed(input()))
    mod = 10**9+7
    memo = [0 for _ in [0]*13]
    m13 = [(10**i) % 13 for i in range(12)]
    memo[0] = 1
    for i in range(len(s)):
        memo2 = np.zeros(13)
        a = m13[i % 12]
        if s[i] == "?":
            list_ = np.array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
        else:
            list_ = np.array([int(s[i])])
        list_ = a*list_ % 13
        for l in list_:
            for j in range(13):
                memo2[(l+j) % 13] += memo[j]
        memo = memo2 % mod
    print(int(memo[5]))


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = list(reversed(input()))
    mod = 10**9+7
    memo = [0 for _ in [0]*13]
    m13 = [(10**i) % 13 for i in range(12)]
    memo[0] = 1
    for i in range(len(s)):
        memo2 = [0 for _ in [0]*13]
        a = m13[i % 12]
        if s[i] == "?":
            list_ = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        else:
            list_ = [int(s[i])]
        list_ = [(a*j) % 13 for j in list_]
        for l in list_:
            for j in range(13):
                memo2[(l+j) % 13] += memo[j]
        memo = [j % mod for j in memo2]
    print(memo[5])


main()

Submission status: Time Limit Exceeded

Solution code:
#%%
S = list(input())
hatena = S.count('?')
hatena_list = [len(S)-1-i for i, x in enumerate(S) if x == '?']

l = [[0]*13 for _ in range(hatena+1)]

SS = S
for i in range(len(S)):
    if SS[i] == '?':
        SS[i] = '0'
SS_13 = int(''.join(SS))%13
l[0][SS_13] = 1

def function(x):
    if x<0:
        x = 13+x
    return x

for i in range(1,hatena+1):
    s = hatena_list[i-1]
    for j in range(0,10):
        SS_13 = 10**s * j %13
        for k in range(0,13):
            l[i][k] += l[i-1][function(k-SS_13)] % 1000000007
            l[i][k] %= 1000000007

        
print(l[-1][5])


#%%

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import csr_matrix


def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7
    
    DP_table = [[0] for i in range(13)]
    
    # 初期化
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[i][0] = 1
    else:
        DP_table[int(digit)][0] = 1
    
    DP_table = csr_matrix(DP_table, dtype=int)
        
    transition_matrixes = {}
    for multiplier in range(13):
        for digit in range(10):
            transition_matrix = [[0 for i in range(13)] for j in range(13)]
            for k in range(13):
                transition_matrix[(digit * multiplier + k) % 13][k] = 1
            transition_matrixes[(multiplier, digit)] = csr_matrix(
                transition_matrix, dtype=int)

    for multiplier in range(13):
        transition_matrixes[multiplier] = csr_matrix(
            [[0 for i in range(13)] for j in range(13)], dtype=int)
        for digit in range(10):
            transition_matrixes[multiplier] = transition_matrixes[multiplier]\
            + transition_matrixes[(multiplier, digit)]
            
    # DP
    multiplier = 1
    for i in range(1, len(S)):
        multiplier = multiplier * 10 % 13
        digit = S[i]
        if digit == '?':
            transition_matrix = transition_matrixes[multiplier]
        else:
            transition_matrix = transition_matrixes[(multiplier, int(digit))]
        
        DP_table = transition_matrix * DP_table
        DP_table = DP_table.toarray() % MOD
        DP_table = csr_matrix(DP_table)

    print(int(DP_table[5][0].toarray()))

    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7
    
    DP_table = np.zeros(13)
    
    # 初期化
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[i] = 1
    else:
        DP_table[int(digit)] = 1
    
    # DP
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier = multiplier * 10 % 13
        if digit == '?':
            transition_matrix = np.zeros((13, 13))
            for j in range(10):
                for k in range(13):
                    transition_matrix[(j * multiplier + k) % 13, k] += 1
        else:
            transition_matrix = np.zeros((13, 13))
            devided = int(digit) * multiplier
            for k in range(13):
                transition_matrix[(devided + k) % 13, k] = 1
        
        DP_table = np.dot(transition_matrix, DP_table)
        DP_table %= MOD

    print(int(DP_table[5]))

    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = {(i, j):0 for i in range(1, len(S)+1) for j in range(13)}
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[(1, i)] = 1
    else:
        #DP_table[(1, int(digit))] = 1
        if digit == '0':
            DP_table[(1, 0)] = 1
        elif digit == '1':
            DP_table[(1, 1)] = 1
        elif digit == '2':
            DP_table[(1, 2)] = 1
        elif digit == '3':
            DP_table[(1, 3)] = 1
        elif digit == '4':
            DP_table[(1, 4)] = 1
        elif digit == '5':
            DP_table[(1, 5)] = 1
        elif digit == '6':
            DP_table[(1, 6)] = 1
        elif digit == '7':
            DP_table[(1, 7)] = 1
        elif digit == '8':
            DP_table[(1, 8)] = 1
        else:
            DP_table[(1, 9)] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier = multiplier * 10 % 13
        if digit == '?':
            for j in range(10):
                for k in range(13):
                    DP_table[(i + 1, (j * multiplier + k) % 13)] += DP_table[(i, k)]
                    
        elif digit == '0':
            for k in range(13):
                DP_table[(i + 1, k % 13)] += DP_table[(i, k)]
        elif digit == '1':
            for k in range(13):
                DP_table[(i + 1, (multiplier + k) % 13)] += DP_table[(i, k)]
        elif digit == '2':
            for k in range(13):
                DP_table[(i + 1, (2 * multiplier + k) % 13)] += DP_table[(i, k)]
        elif digit == '3':
            for k in range(13):
                DP_table[(i + 1, (3 * multiplier + k) % 13)] += DP_table[(i, k)]
        elif digit == '4':
            for k in range(13):
                DP_table[(i + 1, (4 * multiplier + k) % 13)] += DP_table[(i, k)]
        elif digit == '5':
            for k in range(13):
                DP_table[(i + 1, (5 * multiplier + k) % 13)] += DP_table[(i, k)]
        elif digit == '6':
            for k in range(13):
                DP_table[(i + 1, (6 * multiplier + k) % 13)] += DP_table[(i, k)]
        elif digit == '7':
            for k in range(13):
                DP_table[(i + 1, (7 * multiplier + k) % 13)] += DP_table[(i, k)]
        elif digit == '8':
            for k in range(13):
                DP_table[(i + 1, (8 * multiplier + k) % 13)] += DP_table[(i, k)]
        else:
            for k in range(13):
                DP_table[(i + 1, (9 * multiplier + k) % 13)] += DP_table[(i, k)]
            

        
        for j in range(13):
            DP_table[(i + 1, j)] %= MOD

    print(DP_table[(len(S), 5)])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = {(i, j):0 for i in range(1, len(S)+1) for j in range(13)}
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[(1, i)] = 1
    else:
        DP_table[(1, int(digit))] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier = multiplier * 10 % 13
        if digit == '?':
            for j in range(10):
                for k in range(13):
                    DP_table[(i + 1, (j * multiplier + k) % 13)] += DP_table[(i, k)]
        else:
            for k in range(13):
                DP_table[(i + 1, (int(digit) * multiplier + k) % 13)] += DP_table[(i, k)]
        
        for j in range(13):
            DP_table[(i + 1, j)] %= MOD

    print(DP_table[(len(S), 5)])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = {(i, j):0 for i in range(1, len(S)+1) for j in range(13)}
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[(1, i)] = 1
    else:
        DP_table[(1, int(digit))] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier *= 10
        multiplier %= 13
        if digit == '?':
            for j in range(10):
                for k in range(13):
                    surplus = (j * multiplier + k) % 13
                    DP_table[(i + 1, surplus)] += DP_table[(i, k)]
        else:
            for k in range(13):
                surplus = (int(digit) * multiplier + k) % 13
                DP_table[(i + 1, surplus)] += DP_table[(i, k)]
        
        for j in range(13):        
            DP_table[(i + 1, j)] %= MOD
                
    print(DP_table[(len(S), 5)])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = {(i, j):0 for i in range(1, len(S)+1) for j in range(13)}
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[(1, i)] = 1
    else:
        DP_table[(1, int(digit))] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier *= 10
        multiplier %= 13
        if digit == '?':
            for j in range(10):
                for k in range(13):
                    surplus = (j * multiplier + k) % 13
                    DP_table[(i + 1, surplus)] += DP_table[(i, k)]
                    DP_table[(i + 1, surplus)] %= MOD
        else:
            for k in range(13):
                surplus = (int(digit) * multiplier + k) % 13
                DP_table[(i + 1, surplus)] += DP_table[(i, k)]
                DP_table[(i + 1, surplus)] %= MOD
                
    print(DP_table[(len(S), 5)])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = {(i, j):0 for i in range(1, len(S)+1) for j in range(13)}
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[(1, i)] = 1
    else:
        DP_table[(1, int(digit))] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier *= 10
        multiplier %= 13
        if digit == '?':
            for j in range(10):
                devided = j * multiplier
                for k in range(13):
                    surplus = (devided + k) % 13
                    DP_table[(i + 1, surplus)] += DP_table[(i, k)] % MOD
                    DP_table[(i + 1, surplus)] %= MOD
        else:
            for k in range(13):
                surplus = (int(digit) * multiplier + k) % 13
                DP_table[(i + 1, surplus)] += DP_table[(i, k)] % MOD
                DP_table[(i + 1, surplus)] %= MOD
                
    print(DP_table[(len(S), 5)])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = defaultdict(int)
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[(1, i)] = 1
    else:
        DP_table[(1, int(digit))] = 1
    
    power_ten = 1
    for i in range(1, len(S)):
        digit = S[i]
        power_ten *= 10
        if digit == '?':
            for j in range(10):
                devided = j * power_ten
                for k in range(13):
                    surplus = (devided + k) % 13
                    DP_table[(i + 1, surplus)] += DP_table[(i, k)] % MOD
                    DP_table[(i + 1, surplus)] %= MOD
        else:
            for k in range(13):
                surplus = (int(digit) * power_ten + k) % 13
                DP_table[(i + 1, surplus)] += DP_table[(i, k)] % MOD
                DP_table[(i + 1, surplus)] %= MOD
                
    print(DP_table[(len(S), 5)])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def main():
    S = input()
    S = S[::-1]
    MOD = 10**9 + 7

    DP_table = defaultdict(int)
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[(1, i)] = 1
    else:
        DP_table[(1, int(digit))] = 1
    
    power_ten = 1
    for i in range(1, len(S)):
        digit = S[i]
        power_ten *= 10
        if digit == '?':
            for j in range(10):
                devided = j * power_ten
                for k in range(13):
                    surplus = (devided + k) % 13
                    DP_table[(i + 1, surplus)] += DP_table[(i, k)] % MOD
                    DP_table[(i + 1, surplus)] %= MOD
        else:
            for k in range(13):
                surplus = (int(digit) * power_ten + k) % 13
                DP_table[(i + 1, surplus)] += DP_table[(i, k)] % MOD
                DP_table[(i + 1, surplus)] %= MOD
                
    print(DP_table[(len(S), 5)])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import heapq
import math
import queue
import sys
from collections import defaultdict


def main():
    S = input()
    S = S[::-1]
    MOD = 10**9 + 7

    DP_table = defaultdict(int)
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[(1, i)] = 1
    else:
        DP_table[(1, int(digit))] = 1
    
    power_ten = 1
    for i in range(1, len(S)):
        digit = S[i]
        power_ten *= 10
        if digit == '?':
            for j in range(10):
                devided = j * power_ten
                for k in range(13):
                    surplus = (devided + k) % 13
                    DP_table[(i + 1, surplus)] += DP_table[(i, k)] % MOD
                    DP_table[(i + 1, surplus)] %= MOD
        else:
            for k in range(13):
                surplus = (int(digit) * power_ten + k) % 13
                DP_table[(i + 1, surplus)] += DP_table[(i, k)] % MOD
                DP_table[(i + 1, surplus)] %= MOD
                
    print(DP_table[(len(S), 5)])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline


def main():
    mod = 10**9+7
    S = input().strip()
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] = 1
    for n in range(N):
        c = S[N-n-1]
        m = 10**n % 13
        for i in range(10):
            if c == "?" or int(c) == i:
                for j in range(13):
                    dp[n+1][(j + i*m) % 13] += dp[n][j] % mod
    print(dp[N][5] % mod)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline


def main():
    mod = 10**9+7
    S = input().strip()
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] = 1
    for n in range(N):
        c = S[N-n-1]
        m = 10**n
        for i in range(10):
            if c == "?" or int(c) == i:
                for j in range(13):
                    dp[n+1][(j + i*m) % 13] += dp[n][j] % mod
    print(dp[N][5] % mod)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline


def main():
    mod = 10**9+7
    S = input().strip()
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] = 1
    for n in range(N):
        c = S[N-n-1]
        for i in range(10):
            if c == "?" or int(c) == i:
                for j in range(13):
                    dp[n+1][(j + i*10**n) % 13] += dp[n][j] % mod
    print(dp[N][5] % mod)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

init = [0 for i in range(13)]
if s[0] == '?':
  dp = [1] * 10 + [0] * 3
else:
  dp = [0 for i in range(13)]
  dp[int(s[0])] = 1

for c in s[1:]:
  d = init.copy()
  if c == '?':
    for i in range(13):
      for j in range(10):
        idx = (i * 10 + j) % 13
        d[idx] = (dp[i] + d[idx]) % mod 
  else :
    for i in range(13):
      idx = (i * 10 + int(c)) % 13
      d[idx] = (dp[i] + d[idx]) % mod
  dp = d.copy()
print(dp[5])

Submission status: Time Limit Exceeded

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

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] != "?":
    t = int(s[i])
    for j in range(13):
      dp[i+1][(10*j+t)%13] += dp[i][j]
  else:
    for k in range(10):
      for j in range(13):
        dp[i+1][(10*j+k)%13] += dp[i][j]
print(dp[n][5]%(10**9+7))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

dp=[[0]*13 for i in range(n)]
m=[0]*(n-1)+[1]
for i in range(n-1):
    m[-i-2]=m[-i-1]*10%13

if s[0]!='?':
    a=int(s[0])*m[0]%13
    dp[0][a]=1
else:
    for k in range(10):
        a=k*m[0]%13
        dp[0][a]=1

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

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
n = len(S)
mod = 10**9 + 7
pow10 = [1]
for i in range(1,n):
    x = pow10[-1]
    y = 10*x%13
    pow10.append(y)
dp = [[0 for i in range(13)]for j in range(n+1)]
dp[0][0] = 1
for i in range(n):
    d = S[-i-1]
    if d == '?':
        for j in range(10):
            s = (pow10[i]*j)%13
            for t in range(13):
                r = (s+t)%13
                dp[i+1][r] = (dp[i+1][r] + dp[i][t])%mod
    else:
        j = int(d)
        s = (pow10[i]*j)%13
        for t in range(13):
            r = (s+t)%13
            dp[i+1][r] = (dp[i+1][r] + dp[i][t])%mod
print(dp[n][5])

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from operator import itemgetter
d = np.array(list(map(itemgetter(0),sorted(enumerate(i*10%13 for i in range(13)),key=itemgetter(1)))))

MOD = 10**9+7
def main(S):
    M = np.zeros(13, dtype=np.int64)
    if S[0] == "?":
        for j in range(10):
            M[j] = 1
    else:
        M[int(S[0])] = 1
    for s in S[1:]:
        M0 = np.zeros(13, dtype=np.int64)
        if s == "?":
            for j in range(10):
                M0[:] += np.roll(M[d], j)
        else:
            M0[:] = np.roll(M[d], int(s))
        M = M0
        for i in range(13):
            M[i] %= MOD
    return M[5]

if __name__ == "__main__":
    print(main(input()))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
d = np.array([i*10%13 for i in range(13)])

MOD = 10**9+7
def main(S):
    M = np.zeros(13, dtype=np.int64)
    if S[0] == "?":
        for j in range(10):
            M[j] = 1
    else:
        M[int(S[0])] = 1
    for s in S[1:]:
        M0 = np.zeros(13, dtype=np.int64)
        if s == "?":
            for i in range(13):
                for j in range(10):
                    M0[(10*i+j)%13] += M[i]
        else:
            for i in range(13):
                M0[(10*i+int(s))%13] += M[i]
        M = M0
        for i in range(13):
            M[i] %= MOD
    return M[5]

if __name__ == "__main__":
    print(main(input()))

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
S = input()
M = [0] * 13
if S[0] == "?":
    for j in range(10):
        M[j] = 1
else:
    M[int(S[0])] = 1
for s in S[1:]:
    M0 = [0] * 13
    if s == "?":
        for j in range(10):
            for i in range(13):
                M0[(10*i+j)%13] += M[i]
    else:
        for i in range(13):
            M0[(10*i+int(s))%13] += M[i]
    M = M0
    for i in range(13):
        M[i] %= MOD
print(M[5])