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():
    n = 13
    mod = 1000000007
    r = 5
    in_str = input()

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

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

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

    print(ans_list[r] % mod)


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


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


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


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

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

        ans_list = list(map(lambda x: x % mod, ans_list))

    print(ans_list[r] % mod)


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


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


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


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

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

        ans_list = list(map(lambda x: x % mod, ans_list))

    print(ans_list[r] % mod)


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


def add(list1, list2):
    return list(map(sum, zip(list1, list2)))


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


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = 13
    mod = 1000000007
    r = 5

    s_list = list(reversed(input()))

    #amari_list = amari(n)

    amari_list = []
    tmp = amari(n)
    for i in range(len(tmp)):
        amari_list.append([j * tmp[i % len(tmp)] % n for j in range(10)])

    ans_list = initial(s_list[0], n)

    for i, s in enumerate(s_list):
        if i == 0:
            continue
        if s == "?":
            tmp_list, ans_list = ans_list, [0]*n
            for j in range(10):
                #t = j * amari_list[i % len(amari_list)] % n
                t = amari_list[i % len(tmp)][j]
                ans_list = add(ans_list, shift(t, tmp_list))
        else:
            #t = int(s) * amari_list[i % len(amari_list)] % n
            t = amari_list[i % len(tmp)][int(s)]
            ans_list = shift(t, ans_list)

        ans_list = list(map(lambda x: x % mod, ans_list))

    print(ans_list[r] % mod)


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


def add(list1, list2):
    return list(map(sum, zip(list1, list2)))


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


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = 13
    mod = 1000000007
    r = 5

    s_list = list(reversed(input()))

    amari_list = amari(n)
    amari_len = len(amari_list)

    ans_list = initial(s_list[0], n)

    for i, s in enumerate(s_list):
        if i == 0:
            continue
        if s == "?":
            tmp_list, ans_list = ans_list, [0]*n
            for j in range(10):
                t = j * amari_list[i % amari_len] % n
                ans_list = add(ans_list, shift(t, tmp_list))
                ans_list = list(map(lambda x: x % mod, ans_list))
        else:
            t = int(s) * amari_list[i % amari_len] % n
            ans_list = shift(t, ans_list)

    print(ans_list[r] % mod)


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


def add(list1, list2):
    return list(map(sum, zip(list1, list2)))


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


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = 13
    mod = 1000000007
    r = 5

    s_list = list(reversed(input()))

    amari_list = amari(n)
    amari_len = len(amari_list)

    ans_list = initial(s_list[0], n)

    for i, s in enumerate(s_list):
        if i == 0:
            continue
        if s == "?":
            tmp_list, ans_list = ans_list, [0]*n
            for j in range(10):
                t = j * amari_list[i % amari_len] % n
                ans_list = add(ans_list, shift(t, tmp_list))
        else:
            t = int(s) * amari_list[i % amari_len] % n
            ans_list = shift(t, ans_list)

        ans_list = list(map(lambda x: x % mod, ans_list))

    print(ans_list[r] % mod)


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


def add(list1, list2):
    return list(map(sum, zip(list1, list2)))


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


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = 13
    mod = 1000000007
    r = 5

    s_list = list(reversed(input()))

    amari_list = amari(n)
    amari_len = len(amari_list)

    ans_list = initial(s_list[0], n)

    for i, s in enumerate(s_list):
        if i == 0:
            continue
        if s == "?":
            tmp_list, ans_list = ans_list, [0]*n
            for j in range(10):
                t = j * amari_list[i % amari_len] % n
                ans_list = add(ans_list, shift(t, tmp_list))
        else:
            t = int(s)*(10**i) % n
            ans_list = shift(t, ans_list)

        ans_list = list(map(lambda x: x % mod, ans_list))

    print(ans_list[r] % mod)


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


def add(list1, list2):
    return list(map(sum, zip(list1, list2)))


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


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


if __name__ == '__main__':
    main()

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]=='?': #?のときは各値(0～9)について更新する
   for j in range(10):
     for k in range(13):
       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) #最後まで更新を行ったときのあまりが5となる数の個数が答え

Submission status: Time Limit Exceeded

Solution code:
S = input()

dp = [[0 for j in range(13)] for i in range(len(S)+1)]
dp[0][0] = 1
M = 10**9+7

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

ans = dp[-1][5] % M
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=input()
ans=0
last=[0]*13
l=len(s)
last[0]=1
MOD=int(1e9+7)
for i in range(l-1,-1,-1):
    curr=[0]*13
    if s[i]=='?':
        for j in range(13):
            if last[j]>=1:
                for k in range(10):
                    xyz=(j+k*pow(10,l-i-1,13))%13
                    curr[xyz]+=last[j]
                    curr[xyz]%=MOD
    else:
        for j in range(13):
            xyz=(j+(ord(s[i])-ord('0'))*pow(10,l-i-1,13))%13
            curr[xyz]+=last[j]
            curr[xyz]%=MOD
    # print(i,s[i])
    # print(last)
    # print(curr)
    last=curr
print(last[5]%MOD)

Submission status: Time Limit Exceeded

Solution code:
S = input()

dp = [[0 for j in range(13)] for i in range(len(S)+1)]
dp[0][0] = 1
M = 10**9+7

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

ans = dp[-1][5] % M
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

dp = [[0 for j in range(13)] for i in range(len(S)+1)]
dp[0][0] = 1
M = 10**9+7

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

ans = dp[-1][5] % M
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

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

ans = dp[-1][5] % (10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve(string):
    n = len(string)
    q_pos = [i for i in range(n) if string[n - i - 1] == "?"]
    table = [[0] * 13 for _ in range(2)]
    table[0][int(string.replace("?", "0")) % 13] = 1
    for i in range(len(q_pos)):
        base = pow(10, q_pos[i], 13)
        for j in range(13):
            for k in range(10):
                table[1][(j + k * base) % 13] += table[0][j]
        for j in range(13):
            table[1][j] %= (10**9 + 7)
        table[0] = table[1]
        table[1] = [0] * 13
    return str(table[0][5])


if __name__ == '__main__':
    print(solve(input()))

Submission status: Time Limit Exceeded

Solution code:
def solve(string):
    n = len(string)
    q_pos = [i for i in range(n) if string[n - i - 1] == "?"]
    table = [[0] * 13 for _ in range(2)]
    table[0][int(string.replace("?", "0")) % 13] = 1
    for i in range(len(q_pos)):
        base = pow(10, q_pos[i], 13)
        for j in range(13):
            for k in range(10):
                table[1][(j + k * base) % 13] += table[0][j]
        table[0] = table[1]
        table[1] = [0] * 13
    return str(table[0][5] % (10**9 + 7))


if __name__ == '__main__':
    print(solve(input()))

Submission status: Time Limit Exceeded

Solution code:
def solve(string):
    n = len(string)
    q_pos = [i for i in range(n) if string[n - i - 1] == "?"]
    table = [[0] * 13 for _ in range(len(q_pos) + 1)]
    table[0][int(string.replace("?", "0")) % 13] = 1
    for i in range(len(q_pos)):
        base = 10**q_pos[i] % 13
        for j in range(13):
            for k in range(10):
                table[i + 1][(j + k * base) % 13] += table[i][j]
    return str(table[-1][5] % (10**9 + 7))


if __name__ == '__main__':
    print(solve(input()))

Submission status: Time Limit Exceeded

Solution code:
def solve(string):
    n = len(string)
    q_pos = [i for i in range(n) if string[n - i - 1] == "?"]
    table = [[0] * 13 for _ in range(len(q_pos) + 1)]
    table[0][int(string.replace("?", "0")) % 13] = 1
    for i in range(len(q_pos)):
        base = pow(10, q_pos[i], 13)
        for j in range(13):
            for k in range(10):
                table[i + 1][(j + k * base) % 13] += table[i][j]
    return str(table[-1][5] % (10**9 + 7))


if __name__ == '__main__':
    print(solve(input()))

Submission status: Time Limit Exceeded

Solution code:
def solve(string):
    q_pos = [i for i, s in enumerate(string[::-1]) if s == "?"]
    table = [[0] * 13 for _ in range(len(q_pos) + 1)]
    table[0][int(string.replace("?", "0")) % 13] = 1
    for i in range(len(q_pos)):
        base = pow(10, q_pos[i], 13)
        for j in range(13):
            for k in range(10):
                table[i + 1][(j + k * base) % 13] += table[i][j]
    return str(table[-1][5] % (10**9 + 7))


if __name__ == '__main__':
    print(solve(input()))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

A = list(input())
NUM=13

DP = np.zeros((len(A),NUM), dtype=np.int64)
ANS = np.zeros(NUM, dtype=np.int64)


for i in range(len(A)):
        if(A[i]=="?"):
                for j in range(10):
                        DP[i][(j*(10**(len(A)-i-1)))%NUM]+=1
        else:
                DP[i][(int(A[i])*(10**(len(A)-i-1)))%NUM]+=1

for i in range(len(A)-1,0,-1):    
        for j in range(NUM):
                for k in range(NUM):
                        ANS[j] += DP[i][(k)%NUM]*DP[i-1][(NUM-k+j)%NUM]
                ANS[j]=ANS[j]%(10**9+7)
        DP[i-1] = ANS[:]
        ANS = [0]*NUM

ANS = DP[0][:]
print(ANS[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

A = list(input())
NUM=13

DP = np.zeros((len(A),NUM), dtype=np.int64)
ANS = np.zeros(NUM, dtype=np.int64)


for i in range(len(A)):
        if(A[i]=="?"):
                for j in range(10):
                        DP[i][(j * (10**(len(A)-i-1)))%NUM]+=1
        else:
                #print((int(A[i])*(10**(len(A)-i-1)))%NUM)
                DP[i][(int(A[i])*(10**(len(A)-i-1)))%NUM]+=1

for i in range(len(A)-1,0,-1):    
        for j in range(NUM):
                for k in range(NUM):
                        ANS[j] += DP[i][(k)%NUM]*DP[i-1][(NUM-k+j)%NUM]
                        ANS[j]=ANS[j]%(10**9+7)
        DP[i-1] = ANS[:]
        ANS = [0]*NUM

ANS = DP[0][:]

#print(ANS)
print(ANS[5])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

dp = [[1]+[0]*12]
MOD = 10**9+7

for i in range(1,len(S)+1):
  s = S[i-1]
  dp += [[0]*13]
  if s=='?':
    for j in range(13):
      for h in range(10):
        x = h*(10**(i-1))%13
        dp[i][(j+x)%13] += dp[i-1][j]
    for j in range(13):
      dp[i][j] = dp[i][j]%MOD
  else:
    c = int(s)
    x = c*(10**(i-1))%13
    for j in range(13):
      dp[i][(j+x)%13] = dp[i-1][j]
    for j in range(13):
      dp[i][j] = dp[i][j]%MOD
print(dp[-1][5])

Submission status: Time Limit Exceeded

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

dp = [[0]*13]
MOD = 10**9+7

for i in range(1,len(S)+1):
  s = S[i-1]
  dp += [[0]*13]
  if s=='?':
    if i==1:
      for j in range(10):
        dp[i][j] = 1
    else:
      for j in range(13):
        for h in range(10):
          x = h*(10**(i-1))%13
          dp[i][j] += dp[i-1][(j-x)%13]
        dp[i][j] = dp[i][j]%MOD
  else:
    c = int(s)
    x = c*(10**(i-1))%13
    if i==1:
      dp[i][c]=1
    else:
      for j in range(13):
        dp[i][j] = dp[i-1][(j-x)%13]
print(dp[-1][5])

Submission status: Time Limit Exceeded

Solution code:
s=input()
l=len(s);mod=10**9+7
dp=[[0]*13 for i in range(l)]
rem=[1,10,9,12,3,4]
for i in range(l)[::-1]:
  dig=(l-i-1)%6
  if s[i]=="?":
    if i==l-1:
      for j in range(10):
        dp[-1][(j*rem[dig])%13]=1
    else:
      for j in range(10):
        for h in range(13):
          dp[i][(h+j*rem[dig])%13]+=dp[i+1][h]
          dp[i][(h+j*rem[dig])%13]%=mod
  else:
    a=int(s[i])
    if i==l-1:
      dp[i][(a*rem[dig])%13]=1
    else:
      for j in range(13):
        dp[i][(j+a*rem[dig])%13]+=dp[i+1][j]
        dp[i][(j+a*rem[dig])%13]%=mod
print(dp[0][5])

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
n = len(S)
dp = [[0] * 13 for _ in range(n + 1)]

MOD = 10 ** 9 + 7

def solve():
    res = 0
    dp[0][0] = 1
    for i in range(n): #n文字順番に確かめる
        if S[i] == '?': #i文字目が自由のとき
            c = -1
        else:
            c = int(S[i])
        
        for j in range(10):
            if c != -1 and c != j:
                continue
            for k in range(13):
                dp[i + 1][(k * 10 + j) % 13] += dp[i][k]
        
        for j in range(13):
            dp[i + 1][j] %= MOD
    # print (dp)
    res = dp[n][5]
    return res

print (solve())

Submission status: Time Limit Exceeded

Solution code:
s=input()
mod = 1000000007
 
dp = [[0 for l in range(13)] for m in range(len(s)+1)]
dp[0][0] = 1
P=[]
for i in range(1,13):
  P.append(10**(int((i-1)%12))%13)
for i in range(1,len(s)+1):
  p = P[i%12-1]
  if s[-i] == '?':
    for j in range(10):
      for k in range(13):
        dp[i][(k+j*p)%13] += dp[i-1][k]
        dp[i][(k+j*p)%13] %mod
  else:
    for k in range(13):
      dp[i][(int(s[-i])*p +k)%13] += dp[i-1][k]
      dp[i][(int(s[-i])*p +k)%13] %mod

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
s=input()
mod = 1000000007

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

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

Submission status: Time Limit Exceeded

Solution code:
s=input()
mod = 1000000007

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

print(dp[len(s)][5] %mod)
'''
for i in range(13):
  print(i,dp[len(s)][i] %mod )
  '''

Submission status: Time Limit Exceeded

Solution code:
s=input()
mod = 1000000007

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

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    s_list = list(input())
    s_list.reverse()

    ans_list = [1]*10 + [0]*3 if s_list[0] == "?" else initial(int(s_list[0]))

    for i, s in enumerate(s_list):
        if i == 0:
            continue
        if s == "?":
            tmp_list = [0]*13
            for j in range(10):
                r = j * (10**i) % 13
                tmp_list = add(tmp_list, shift(r, ans_list))
            ans_list = tmp_list
        else:
            r = int(s)*(10**i) % 13
            ans_list = shift(r, ans_list)

    print(ans_list[5] % 1000000007)


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


def add(list1, list2):
    return list(map(sum, zip(list1, list2)))


def initial(n):
    return [(1 if i == n else 0) for i in range(13)]


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD =  1000000007
res = 0
a = input()
n = len(a)
A = 13
dp=[[0 for i in range(A+1)] for j in range(n+1)]
dp[0][0] = 1
for i in range(n):
    c = 0
    if a[i] == '?': c = -1
    else: c = int(a[i])
    
    for j in range(10):
        if c != -1 and c != j: continue
        for ki in range(13):
            dp[i+1][(ki*10 + j)% 13] += dp[i][ki]
        
    for j in range(13):
        dp[i+1][j] %= MOD

print(dp[n][5])

Submission status: Time Limit Exceeded

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

				# print(j)
				if j-(k*(10**(n-i-1)))%13>=0:
					dp[i+1][j]+=dp[i][j-(k*(10**(n-i-1)))%13]%mod
				else:
					dp[i+1][j]+=dp[i][j-(k*(10**(n-i-1)))%13+13]%mod
				
# print(dp)
# print(s)
print(dp[n][5]%mod)

Submission status: Time Limit Exceeded

Solution code:
S = input()
INF = 10 ** 9 + 7
mod = [1,10,9,12,3,4]
dp = [[0 for _ in range(13)] for l in range(len(S))]
S_li = [_ for _ in S]
S_li = S_li[::-1]
if S_li[0] == '?':
    dp[0][0:10] = [1,1,1,1,1,1,1,1,1,1]
else:
    dp[0][int(S_li[0])] = 1
for _ in range(1,len(S)):
    if S_li[_] == '?':
        for x in range(10):
            for y in range(13):
                dp[_][(x * mod[_ % 6] + y) % 13] += dp[_ - 1][y] % INF
    else:
        for y in range(13):
            dp[_][(int(S_li[_]) * mod[_ % 6] + y) % 13] += dp[_ - 1][y] % INF
print(dp[-1][5] % INF)

Submission status: Time Limit Exceeded

Solution code:
S = input()
INF = 10 ** 9 + 7
dp = [[0 for _ in range(13)] for l in range(len(S))]
S_li = [_ for _ in S]
S_li = S_li[::-1]
if S_li[0] == '?':
    dp[0][0:10] = [1,1,1,1,1,1,1,1,1,1]
else:
    dp[0][int(S_li[0])] = 1
for _ in range(1,len(S)):
    if S_li[_] == '?':
        for x in range(10):
            for y in range(13):
                dp[_][((x * (10 ** (_ % 6))) + y) % 13] += dp[_ - 1][y] % INF
    else:
        for y in range(13):
            dp[_][((int(S_li[_]) * (10 ** (_ % 6))) + y) % 13] += dp[_ - 1][y] % INF
print(dp[-1][5] % INF)

Submission status: Time Limit Exceeded

Solution code:
S = input()
INF = 10 ** 9 + 7
dp = [[0 for _ in range(13)] for l in range(len(S))]
S_li = [_ for _ in S]
S_li = S_li[::-1]
if S_li[0] == '?':
    dp[0][0:10] = [1,1,1,1,1,1,1,1,1,1]
else:
    dp[0][int(S_li[0])] = 1
for _ in range(1,len(S)):
    if S_li[_] == '?':
        for x in range(10):
            for y in range(13):
                dp[_][((x * (10 ** _)) + y) % 13] += dp[_ - 1][y] % INF
    else:
        for y in range(13):
            dp[_][((int(S_li[_]) * (10 ** _)) + y) % 13] += dp[_ - 1][y] % INF
print(dp[-1][5] % INF)

Submission status: Time Limit Exceeded

Solution code:
S = input()
dp = [[0 for _ in range(13)] for l in range(len(S))]
S_li = [_ for _ in S]
S_li = S_li[::-1]
if S_li[0] == '?':
    dp[0][0:10] = [1,1,1,1,1,1,1,1,1,1]
else:
    dp[0][int(S_li[0])] = 1
for _ in range(1,len(S)):
    if S_li[_] == '?':
        for x in range(10):
            for y in range(13):
                dp[_][((x * (10 ** _)) + y) % 13] += dp[_ - 1][y] 
    else:
        for y in range(13):
            dp[_][((int(S_li[_]) * (10 ** _)) + y) % 13] += dp[_ - 1][y] 
print(dp[-1][5] % ((10 ** 9) + 7))

Submission status: Time Limit Exceeded

Solution code:
import itertools
 
s = str(input())
 
n = len(s)
dp = [[0]*13 for i in range(n+1)]
dp[0][0] = 1
 
M = 1
INF = 10 ** 9 + 7
      
for i in range(n):
  if s[n-1-i] == '?':
    for k, j in itertools.product(range(10), range(13)):
      x = (j+k*10**i)%13
      dp[i+1][x] += dp[i][j]
      dp[i+1][x] %= INF
  else:
    for j in range(13):
      x = (j+int(s[n-1-i])*10**i)%13
      dp[i+1][x] += dp[i][j]
      dp[i+1][x] %= INF
  #M = (M*10)%13

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
 
s = str(input())
 
n = len(s)
dp = [[0]*13 for i in range(n+1)]
dp[0][0] = 1

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
 
s = str(input())
 
n = len(s)
dp = [[0]*13 for i in range(n+1)]
dp[0][0] = 1
      
for i in range(n):
  if s[n-1-i] == '?':
    for k, j in itertools.product(range(10), range(13)):
      x = (j+k*10**i)%13
      dp[i+1][x] += dp[i][j]
  else:
    for j in range(13):
      x = (j+int(s[n-1-i])*10**i)%13
      dp[i+1][x] += dp[i][j]

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

Submission status: Time Limit Exceeded

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

R10 = range(10)
R13 = range(13)

S = input()
R = [[(M * 10 + N) % 13 for N in R10] for M in R13]

MOD =[1]+[0]*12


for i,D in enumerate(S):
    NMOD = [0] * 13
    C = -1
    if D == '?':
        for N in R10:
            for M in R13:
                NM = R[M][N]
                NMOD[NM] += MOD[M]
            #end for
        #end for
    else:
        C = int(D)
        for M in R13:
            NM = R[M][C]
            NMOD[NM] += MOD[M]
        #end for
    #end if
    MOD = [NMOD[M]%1000000007 for M in R13]
#end for

print(MOD[5])

Submission status: Time Limit Exceeded

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

S = input()

MOD =[1,0,0,0,0,0,0,0,0,0,0,0,0]
NMOD =[0,0,0,0,0,0,0,0,0,0,0,0,0]

R10 = range(10)
R13 = range(13)

for i,D in enumerate(S):
    C = -1
    if D == '?':
        for N in R10:
            for M in R13:
                NM = (M * 10 + N) % 13
                NMOD[NM] += MOD[M]
            #end for
        #end for
    else:
        C = int(D)
        for M in R13:
            NM = (M * 10 + C) % 13
            NMOD[NM] += MOD[M]
        #end for
    #end if
    for M in R13:
        MOD[M] = NMOD[M]%1000000007
        NMOD[M] = 0
    #end for
#end for

print(MOD[5])

Submission status: Time Limit Exceeded

Solution code:
import itertools

s = str(input())

n = len(s)
dp = [[0]*13 for i in range(n)]
      
for i in range(n):
  if i != 0:
    if s[i] == '?':
      for k, j in itertools.product(range(10), range(13)):
        x = (j+k*10**(n-1-i))%13
        dp[i][x] += dp[i-1][j]
    else:
      for j in range(13):
        x = (j+int(s[i])*10**(n-1-i))%13
        dp[i][x] += dp[i-1][j]
  else:
    if s[i] == '?':
      for k in range(10):
        x = (k*10**(n-1-i))%13
        dp[i][x] += 1
    else:
      x = (int(s[i])*10**(n-1-i))%13
      dp[i][x] += 1

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