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:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
MOD = 10**9+7
old_dp=[0]*13
new_dp=[0]*13
old_dp[0]=1

for c in s:
    for i in range(13):
        if c == '?':
            for d in range(10):
                new_dp[(10*i+d)%13] += old_dp[i]
        else:
            new_dp[(10*i+int(c))%13] += old_dp[i]
    
    old_dp = [x % MOD for x in new_dp]
    new_dp = [0]*13
print(old_dp[5])

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
mod = 10**9+7
dp = [[0]*13 for i in range(n+5)]#dp[i][j] :=先頭i文字を見たとき、その数字を13で割ったあまりがｊであるような場合の数
dp[0][0] = 1#先頭０文字は”０”　で、１３で割ったあまりは０だから　dp[0][0] = 1
for i in range(n):
    for j in range(13):
        if s[i] == "?":
            for d in range(10):
                dp[i+1][(j*10+d)%13] += dp[i][j]
                dp[i+1][(j*10+d)%13] %= mod
                
        else:
            dp[i+1][(j*10+int(s[i]))%13] += dp[i][j]
            dp[i+1][(j*10+int(s[i]))%13] %= mod
ans = dp[n][5]
print(ans)

Submission status: Time Limit Exceeded

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

dp = [0]*13
dp[0] = 1

tmp = 1
for i, s in enumerate(S[::-1]):
    new = [0]*13
    if s == "?":
        for x in range(13):
            for y in range(10):
                next_x = y * tmp + x
                new[next_x % 13] += dp[x]
                new[next_x % 13] %= mod
    else:
        for x in range(13):
            next_x = int(s) * tmp + x
            new[next_x % 13] = dp[x]

    dp = new
    tmp *= 10 % 13

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

Submission status: Time Limit Exceeded

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

dp = [[0]*13 for _ in range(len(S)+1)]
dp[0][0] = 1
cnt = 1

for i, s in enumerate(S[::-1]):
    if s == "?":
        tmp = pow(10, i, 13)
        for x in range(13):
            for y in range(10):
                next_x = y * tmp + x
                dp[i+1][next_x % 13] += dp[i][x]
                dp[i+1][next_x % 13] %= mod
    else:
        for x in range(13):
            next_x = int(s)*10**i+x
            dp[i + 1][next_x % 13] = dp[i][x]


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

Submission status: Time Limit Exceeded

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

dp = [[0]*13 for _ in range(len(S)+1)]
dp[0][0] = 1
cnt = 1

for i, s in enumerate(S[::-1]):
    if s == "?":
        for x in range(13):
            for y in range(10):
                next_x = y * 10 ** i + x
                dp[i+1][next_x % 13] += dp[i][x]
                dp[i+1][next_x % 13] %= mod
    else:
        for x in range(13):
            next_x = int(s)*10**i+x
            dp[i + 1][next_x % 13] = dp[i][x]


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

Submission status: Time Limit Exceeded

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

dp = [[0] * 13 for _ in range(2)]
dp[0][0] = 1
cnt = 1

for i, s in enumerate(S[::-1]):
    dp[cnt] = [0]*13
    if s == "?":
        for j in range(10):
            d = j * (10 ** i) % 13
            for k in range(13):
                x = k + d
                if x >= 13:
                    x -= 13
                dp[cnt][x] += dp[1 - cnt][k]
                dp[cnt][k] %= mod
    else:
        d = int(s) * (10 ** i) % 13
        for j in range(13):
            x = j + d
            if x >= 13:
                x -= 13
            dp[cnt][x] += dp[1 - cnt][j]
            dp[cnt][j] %= mod
    cnt = 1-cnt

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

Submission status: Time Limit Exceeded

Solution code:
S=input()
N=len(S)
mod=13
mod2=10**9+7

#i桁目までみて，あまりがjになるものの個数
dp=[[0]*mod for _ in range(N+1)]

#1桁目
if S[-1]!="?":
    a=int(S[-1])
    for j in range(mod):
        dp[1][a]=1
else:
    for j in range(mod):
        for k in range(10):
            dp[1][k]=1

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

print(dp[-1][5])

Submission status: Time Limit Exceeded

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

def main():
    S = list(str(input()))
    a = len(S)
    dp = [[0 for _ in range(13)] for _ in range(a+1)]
    dp[0][0] = 1
    INF = 10**9+7
    
    for i in range(a):
        if S[i] == "?":
            for j in range(10):
                for k in range(13):
                    dp[i+1][(10*k+j)%13] += dp[i][k]%INF
        else:
            num = int(S[i])
            for k in range(13):
                dp[i+1][(10*k+num)%13] += dp[i][k]%INF
    
    print(dp[-1][5]%INF)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


def fetch_one_line():
    return stdin.readline().rstrip()


def fetch_int_input():
    return [int(s) for s in fetch_one_line().split()]


def fetch_inputs(times):
    return [fetch_one_line() for _ in range(times)]


def fetch_int_inputs(times):
    return [[int(s) for s in fetch_one_line()] for _ in range(times)]


def fetch_ints_inputs(times):
    return [fetch_int_input() for _ in range(times)]


ipt = fetch_one_line()
DIVIDE_NUM = 13
remainds = [[0 for _ in range(DIVIDE_NUM)] for i in range(len(ipt) + 1)]
remainds[0][0] = 1

def transrate(matrix):
    return list(map(list, zip(*matrix)))

def make_remind(latest_remind, digit):
    tmp_remind = [[latest_remind[(j - (i * (digit % 13))) % 13] for j in range(DIVIDE_NUM)]
            for i in range(10)]

    return [sum(t) for t in transrate(tmp_remind)]

for idx, s in enumerate(ipt[::-1]):
    if s == "?":
        digit = pow(10, idx)
        for ti, rm in enumerate(make_remind(remainds[idx], digit)):
            remainds[idx + 1][ti] = rm
    else:
        int_s = int(s)
        digit = pow(10, idx)
        move = (int_s % 13) * (digit % 13)

        new_remaind = [remainds[idx][(i - move) % 13] for i in range(DIVIDE_NUM)]
        for ti, rm in enumerate(new_remaind) :
            remainds[idx + 1][ti] = rm

        # remainds.append(new_remaind)

print(remainds[-1][5] % (pow(10, 9) + 7))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


def fetch_one_line():
    return stdin.readline().rstrip()


def fetch_int_input():
    return [int(s) for s in fetch_one_line().split()]


def fetch_inputs(times):
    return [fetch_one_line() for _ in range(times)]


def fetch_int_inputs(times):
    return [[int(s) for s in fetch_one_line()] for _ in range(times)]


def fetch_ints_inputs(times):
    return [fetch_int_input() for _ in range(times)]


ipt = fetch_one_line()
DIVIDE_NUM = 13
remainds = [[0 for _ in range(DIVIDE_NUM)]]
remainds[0][0] = 1

def transrate(matrix):
    return list(map(list, zip(*matrix)))

def make_remind(latest_remind, digit):
    tmp_remind = [[latest_remind[(j - (i * (digit % 13))) % 13] for j in range(DIVIDE_NUM)]
            for i in range(10)]

    return [sum(t) for t in transrate(tmp_remind)]

for idx, s in enumerate(ipt[::-1]):
    if s == "?":
        digit = pow(10, idx)
        remainds.append(make_remind(remainds[-1], digit))
    else:
        int_s = int(s)
        digit = pow(10, idx)
        move = (int_s % 13) * (digit % 13)
        new_remaind = [remainds[-1][(i - move) % 13] for i in range(DIVIDE_NUM)]
        remainds.append(new_remaind)

print(remainds[-1][5] % (pow(10, 9) + 7))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


def fetch_one_line():
    return stdin.readline().rstrip()


def fetch_int_input():
    return [int(s) for s in fetch_one_line().split()]


def fetch_inputs(times):
    return [fetch_one_line() for _ in range(times)]


def fetch_int_inputs(times):
    return [[int(s) for s in fetch_one_line()] for _ in range(times)]


def fetch_ints_inputs(times):
    return [fetch_int_input() for _ in range(times)]


ipt = fetch_one_line()
DIVIDE_NUM = 13
remainds = [[0 for _ in range(DIVIDE_NUM)]]
remainds[0][0] = 1

def transrate(matrix):
    return list(map(list, zip(*matrix)))

def make_remind(latest_remind, digit):
    tmp_remind = []
    for i in range(10):
        move = i * (digit % 13)
        new_remaind = [0 for _ in range(DIVIDE_NUM)]
        for j in range(DIVIDE_NUM):
            new_remaind[j] = latest_remind[(j - move) % 13]
        tmp_remind.append(new_remaind)

    return [sum(t) for t in transrate(tmp_remind)]

for idx, s in enumerate(ipt[::-1]):
    if s == "?":
        digit = pow(10, idx)
        remainds.append(make_remind(remainds[-1], digit))
    else:
        int_s = int(s)
        digit = pow(10, idx)
        move = (int_s % 13) * (digit % 13)
        new_remaind = [remainds[-1][(i - move) % 13] for i in range(DIVIDE_NUM)]
        remainds.append(new_remaind)

print(remainds[-1][5] % (pow(10, 9) + 7))

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

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

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def main():
    s = S()
    N = len(s)
    dp = [[0 for _ in range(13)] for ___ in range(N)]
    # dp[i][j]: iまでみてあまりがjである数の個数
    for c in range(13):
        if s[0] == '?':
            for k in range(10):
                new_mod = k * (10**(N - 1)) % 13
                dp[0][new_mod] = 1
        else:
            new_mod = int(s[0]) * (10**(N-1)) % 13
            dp[0][new_mod] = 1
    for i in range(1, N):
        c = s[i]
        for j in range(0, 13):
            if c == '?':
                for k in range(10):
                    new_mod = j + int(k) * (10**(N - 1 - i))
                    new_mod %= 13
                    dp[i][new_mod] += dp[i-1][j]
            else:
                new_mod = j + int(c) * (10 ** (N - 1 - i))
                new_mod %= 13
                dp[i][new_mod] += dp[i-1][j]
            dp[i][new_mod] %= mod
    print(dp[N-1][5] % mod)

main()

Submission status: Time Limit Exceeded

Solution code:
S = input().strip()
mod = 10**9+7
n = len(S)
d = [[0]*13 for _ in range(n+1)]
d[n][0] = 1
S = S[::-1]
for i in range(n):
    i = n-i-1
    b = (10**i) % 13
    if S[i] == "?":
        for j in range(10):
            for k in range(13):
                d[i][(k+(j*b))%13] += d[i+1][k]
                d[i][(k+(j*b))%13] %= mod
    else:
        for k in range(13):
            d[i][(k+(int(S[i])*b))%13] += d[i+1][k]
            d[i][(k+(int(S[i])*b))%13] %= mod
print(d[0][5])

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7

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

for i, s in enumerate(S):
  if s == '?':
    R = [j*10**i % 13 for j in range(10)]
    for j in range(13):
      for r in R:
        dp[i+1][(j+r)%13] = (dp[i+1][(j+r)%13] + dp[i][j]) % mod
      
  else:
    s = int(s)
    r = s*10**i % 13
    dp[i+1] = dp[i][-r:] + dp[i][:-r]

print(dp[-1][5])

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7

dp = [1] + [0]*12

for i, s in enumerate(S):
  if s == '?':
    R = [j*10**i % 13 for j in range(1, 10)]
    _dp = dp.copy()
    for r in R:
      dp = [(a1+a2)%mod for a1, a2 in zip(dp, _dp[-r:] + _dp[:-r])]
      
  else:
    s = int(s)
    r = s*10**i % 13
    dp = dp[-r:] + dp[:-r]

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()

    div = 13
    dp = [0] * div
    mod = 1000000007

    # ループカウンタ
    count = 0

    # 0を13で割った時のあまりを格納
    dp[0] = 1
    # print("-" * 50)
    # print("v : {:>20}  ".format(0), end="")
    # print(dp)

    for v in reversed(s):
        tmp_dp = [0] * div
        digit = 10**count

        if v == "?":
            for i in range(10):
                for k in range(div):
                    a = (i * digit + k) % div
                    tmp_dp[a] += dp[k]
                    tmp_dp[a] %= mod
        else:
            int_v = int(v)
            for k in range(div):
                a = (int_v * digit + k) % div
                tmp_dp[a] += dp[k]
                tmp_dp[a] %= mod

        count += 1
        dp = tmp_dp

        # print("v : {:>20}  ".format(s[len(s)-count:]), end="")
        # print(dp)

    print(dp[5] % mod)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

S = input()

MOD = 10 ** 9 + 7
count = 0
S_len = len(S)

dp = [[0 for i in range(13)] for j in range(100006)]
c = -1
if S[0] != '?':
    c = int(S[0])
for j in range(10):
    if c == -1:
        dp[1][j] = 1
    else:
        dp[1][c] = 1

for i in range(2, S_len + 1):
    c = -1
    if S[i - 1] != '?':
        c = ord(S[i - 1]) - ord('0')

    for j in range(10):
        if c != -1 and c != j:
            continue
        for k in range(13):
            dp[i][(k * 10 + j) % 13] += dp[i - 1][k] % MOD


print(dp[S_len][5] % MOD)

Submission status: Time Limit Exceeded

Solution code:

S = input()

MOD = 10 ** 9 + 7
count = 0
S_len = len(S)

dp = [[0 for i in range(13)] for j in range(100006)]
c = -1
if S[0] != '?':
    c = int(S[0])
for j in range(10):
    if c == -1:
        dp[1][j] = 1
    else:
        dp[1][c] = 1

for i in range(2, S_len + 1):
    c = -1
    if S[i - 1] != '?':
        c = ord(S[i - 1]) - ord('0')

    for j in range(10):
        if c != -1 and c != j:
            continue
        for k in range(13):
            dp[i][(k * 10 + j) % 13] += dp[i - 1][k]

    for j in range(10):
        dp[i][j] %= MOD

print(dp[S_len][5])

Submission status: Time Limit Exceeded

Solution code:

S = input()

MOD = 10 ** 9 + 7
count = 0
S_len = len(S)

dp = [[0 for i in range(13)] for j in range(100006)]
c = -1
if S[0] != '?':
    c = int(S[0])
for j in range(10):
    if c == -1:
        dp[1][j] = 1
    else:
        dp[1][c] = 1

for i in range(2, S_len + 1):
    c = -1
    if S[i - 1] != '?':
        c = int(S[i - 1])

    for j in range(10):
        if c != -1 and c != j:
            continue
        for k in range(13):
            dp[i][(k * 10 + j) % 13] += dp[i - 1][k]

    for j in range(10):
        dp[i][j] %= MOD

print(dp[S_len][5])

Submission status: Time Limit Exceeded

Solution code:

S = input()

MOD = 10 ** 9 + 7
count = 0
S_len = len(S)

dp = [[0 for i in range(13)] for j in range(100006)]
c = -1
if S[0] != '?':
    c = int(S[0])
for j in range(10):
    if c == -1:
        dp[1][j] = 1
    else:
        dp[1][c] = 1

for i in range(2, S_len + 1):
    c = -1
    if S[i - 1] != '?':
        c = int(S[i - 1])

    for j in range(13):
        if c == -1:
            for k in range(10):
                dp[i][(j * 10 + k) % 13] += dp[i - 1][j]
        else:
            dp[i][(j * 10 + c) % 13] += dp[i - 1][j]

    for j in range(10):
        dp[i][j] %= MOD

print(dp[S_len][5])

Submission status: Time Limit Exceeded

Solution code:
S=input()
keta=len(S)
import numpy as np
dp=np.zeros((keta,26),dtype=int)
DIV=10**9+7

if S[-1]=="?":
  for i in range(10):
    dp[0][i]=1
else:
  dp[0][int(S[-1])]=1
  
dig=1
for i in range(1,keta):
  dig*=10
  if S[keta-1-i]=="?":
    for k in range(10):
      d=k*dig%13
      dp[i][d:d+13]+=dp[i-1][:13]
      dp[i][:13]+=dp[i][13:]
      dp[i][13:]*=0
      dp[i]%=DIV
  else:
    ch=int(S[keta-1-i])
    d=ch*dig%13
    dp[i][d:d+13]+=dp[i-1][:13]
    dp[i][:13]+=dp[i][13:]
    dp[i][13:]*=0
  dp[i]%=DIV

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

Submission status: Time Limit Exceeded

Solution code:
S=input()
keta=len(S)
import numpy as np
dp=np.zeros((keta,26),dtype=int)
DIV=10**9+7

if S[-1]=="?":
  for i in range(10):
    dp[0][i]=1
else:
  dp[0][int(S[-1])]=1
  
dig=1
for i in range(1,keta):
  dig*=10
  if S[keta-1-i]=="?":
    for k in range(10):
      d=k*dig%13
      dp[i][d:d+13]+=dp[i-1][:13]
      dp[i][:13]+=dp[i][13:]
      dp[i][13:]*=0
  else:
    ch=int(S[keta-1-i])
    d=ch*dig%13
    dp[i][d:d+13]+=dp[i-1][:13]
    dp[i][:13]+=dp[i][13:]
    dp[i][13:]*=0
  dp[i]=dp[i]%DIV

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

Submission status: Time Limit Exceeded

Solution code:
S=input()
keta=len(S)
import numpy as np
dp=np.zeros((keta,26),dtype=int)
DIV=10**9+7

if S[-1]=="?":
  for i in range(10):
    dp[0][i]=1
else:
  dp[0][int(S[-1])]=1
  
dig=1
for i in range(1,keta):
  dig*=10
  if S[keta-1-i]=="?":
    for k in range(10):
      d=k*dig%13
      dp[i][d:d+13]+=dp[i-1][:13]
      dp[i][:13]=dp[i][:13]+dp[i][13:]
      dp[i][13:]*=0
  else:
    ch=int(S[keta-1-i])
    d=ch*dig%13
    dp[i][d:d+13]+=dp[i-1][:13]
    dp[i][:13]=dp[i][:13]+dp[i][13:]
    dp[i][13:]*=0
  dp[i]=dp[i]%DIV

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

Submission status: Time Limit Exceeded

Solution code:
S=input()
keta=len(S)
import numpy as np
dp=np.zeros((keta,13),dtype=int)
DIV=10**9+7

if S[-1]=="?":
  for i in range(10):
    dp[0][i]=1
else:
  dp[0][int(S[-1])]=1
  
def convert(bef,add):
  nex=bef+add
  if nex>=13:
    nex-=13
  return nex
  
dig=1
for i in range(1,keta):
  dig*=10
  if S[keta-1-i]=="?":
    for k in range(10):
      d=k*dig%13
      for j in range(13):
        dp[i][convert(j,d)]+=dp[i-1][j]
  else:
    ch=int(S[keta-1-i])
    d=ch*dig%13
    for j in range(13):
      dp[i][convert(j,d)]+=dp[i-1][j]
  dp[i]=dp[i]%DIV

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

Submission status: Time Limit Exceeded

Solution code:
S=input()
keta=len(S)
import numpy as np
dp=[[0 for j in range(13)] for i in range(keta)]
DIV=10**9+7

if S[-1]=="?":
  for i in range(10):
    dp[0][i]=1
else:
  dp[0][int(S[-1])]=1
  
def convert(bef,add):
  nex=bef+add
  if nex>=13:
    nex-=13
  return nex
  
dig=1
for i in range(1,keta):
  dig*=10
  if S[keta-1-i]=="?":
    for k in range(10):
      d=k*dig%13
      for j in range(13):
        dp[i][convert(j,d)]+=dp[i-1][j]
  else:
    ch=int(S[keta-1-i])
    d=ch*dig%13
    for j in range(13):
      dp[i][convert(j,d)]+=dp[i-1][j]
  for j in range(13):
    dp[i][j]%=DIV

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

Submission status: Time Limit Exceeded

Solution code:
S=input()
keta=len(S)
import numpy as np
dp=[[0 for j in range(13)] for i in range(keta)]
DIV=10**9+7

if S[-1]=="?":
  for i in range(10):
    dp[0][i]=1
else:
  dp[0][int(S[-1])]=1
  
def convert(bef,add):
  nex=bef+add
  if nex>=13:
    nex-=13
  return nex
  
dig=1
for i in range(1,keta):
  dig*=10
  if S[keta-1-i]=="?":
    for k in range(10):
      d=k*dig%13
      for j in range(13):
        dp[i][convert(j,d)]+=dp[i-1][j]
        dp[i][convert(j,d)]%=DIV
  else:
    ch=int(S[keta-1-i])
    d=ch*dig%13
    for j in range(13):
      dp[i][convert(j,d)]+=dp[i-1][j]
      dp[i][convert(j,d)]%=DIV

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

Submission status: Time Limit Exceeded

Solution code:
S=input()
keta=len(S)
import numpy as np
dp=np.zeros((keta,13),dtype=int)
DIV=10**9+7

if S[-1]=="?":
  for i in range(10):
    dp[0][i]=1
else:
  dp[0][int(S[-1])]=1
  
def convert(bef,add):
  nex=bef+add
  if nex>=13:
    nex-=13
  return nex
  
dig=1
for i in range(1,keta):
  dig*=10
  if S[keta-1-i]=="?":
    for k in range(10):
      d=k*dig%13
      for j in range(13):
        dp[i][convert(j,d)]+=dp[i-1][j]
        dp[i][convert(j,d)]%=DIV
  else:
    ch=int(S[keta-1-i])
    d=ch*dig%13
    for j in range(13):
      dp[i][convert(j,d)]+=dp[i-1][j]
      dp[i][convert(j,d)]%=DIV

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

Submission status: Time Limit Exceeded

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

if S[-1]=="?":
  for i in range(10):
    dp[0][i]=1
else:
  dp[0][int(S[-1])]=1
  
def convert(bef,add):
  nex=bef+add
  if nex>=13:
    nex-=13
  return nex
  
dig=1
for i in range(1,keta):
  dig*=10
  if S[keta-1-i]=="?":
    for j in range(13):
      for k in range(10):
        dp[i][convert(j,k*dig%13)]+=dp[i-1][j]
        dp[i][convert(j,k*dig%13)]%=DIV
  else:
    ch=int(S[keta-1-i])
    for j in range(13):
      dp[i][convert(j,ch*dig%13)]+=dp[i-1][j]
      dp[i][convert(j,ch*dig%13)]%=DIV

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

Submission status: Time Limit Exceeded

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

if S[-1]=="?":
  for i in range(10):
    dp[0][i]=1
else:
  dp[0][int(S[-1])]=1
  
def convert(bef,add):
  nex=bef+add
  if nex>=13:
    nex-=13
  return nex
  
for i in range(1,keta):
  if S[keta-1-i]=="?":
    for j in range(13):
      for k in range(10):
        dp[i][convert(j,k*(10**i)%13)]+=dp[i-1][j]
        dp[i][convert(j,k*(10**i)%13)]%=DIV
  else:
    ch=int(S[keta-1-i])
    for j in range(13):
      dp[i][convert(j,ch*(10**i)%13)]+=dp[i-1][j]
      dp[i][convert(j,ch*(10**i)%13)]%=DIV

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

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)]

for i in range(len(S)):
    if S[i] == '?':
        S[i] = '0'
SS_13 = int(''.join(S))%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)%13
        SS_13 *= j
        SS_13 %= 13
        for k in range(0,13):
            l[i][k] += l[i-1][function(k-SS_13)] 
    for j in range(0, 13):
        l[i][j] %= 10 ** 9 + 7
  
print(l[-1][5])



#%%

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)]

for i in range(len(S)):
    if S[i] == '?':
        S[i] = '0'
SS_13 = int(''.join(S))%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)%13
        SS_13 *= j
        SS_13 %= 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:
p = 10**9+7
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x%13
    if m%2==0:
        return (pow(x,m//2)**2)%13
    else:
        return (x*(pow(x,(m-1)//2)**2)%13)%13
S = input().strip()
n = len(S)
A = [0 for _ in range(n)]
for i in range(n):
    A[i] = pow(10,i)
dp = [[0 for _ in range(13)] for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    for j in range(13):
        if S[i]!="?":
            a = int(S[i])
            b = (a*A[n-1-i])%13
            dp[i+1][j] = dp[i][(j-b)%13]
        else:
            for k in range(10):
                b = (k*A[n-1-i])%13
                dp[i+1][j] = (dp[i+1][j]+dp[i][(j-b)%13])%p
print(dp[n][5])

Submission status: Time Limit Exceeded

Solution code:
p = 10**9+7
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x
    if m%2==0:
        return (pow(x,m//2)**2)%13
    else:
        return (x*(pow(x,(m-1)//2)**2)%13)%13
S = input().strip()
n = len(S)
A = [0 for _ in range(n)]
for i in range(n):
    A[i] = pow(10,i)
dp = [[0 for _ in range(13)] for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    for j in range(13):
        if S[i]!="?":
            a = int(S[i])
            b = (a*A[n-1-i])%13
            dp[i+1][j] = dp[i][(j-b)%13]
        else:
            for k in range(10):
                b = (k*A[n-1-i])%13
                dp[i+1][j] = (dp[i+1][j]+dp[i][(j-b)%13])%p
print(dp[n][5])

Submission status: Time Limit Exceeded

Solution code:
p = 10**9+7
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x
    if m%2==0:
        return (pow(x,m//2)**2)%13
    else:
        return (x*(pow(x,(m-1)//2)**2)%13)%13
S = input().strip()
n = len(S)
dp = [[0 for _ in range(13)] for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    for j in range(13):
        if S[i]!="?":
            a = int(S[i])
            b = (a*pow(10,n-1-i))%13
            dp[i+1][j] = dp[i][(j-b)%13]
        else:
            for k in range(10):
                b = (k*pow(10,n-1-i))%13
                dp[i+1][j] = (dp[i+1][j]+dp[i][(j-b)%13])%p
print(dp[n][5])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
MOD = 10**9+7
s = input()
n = len(s)

dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1
b = 1
for i in range(1,n+1):
    if s[n-i] == "?":
        for j in range(10):
            for k in range(13):
                dp[i][(j*b+k)%13] += dp[i-1][k]
    else:
        j = int(s[n-i])
        for k in range(13):
            dp[i][(j*b+k)%13] += dp[i-1][k]
    for k in range(13):
        dp[i][k] %= MOD
    b *= 10
    b %= 13

print(dp[n][5]%MOD)

Submission status: Time Limit Exceeded

Solution code:
rotate = lambda x,y: x[-y:] + x[:-y]
S = input()
mod = 13
amari = 5
dp_tmp = [0]*13
dp_tmp[0] = 1
mul = 1
for s in S[::-1]:
    dp = [0]*13
    if s == "?":
        for n in range(10):
            dp_tmp_roll = rotate(dp_tmp,n*mul%mod)
            for k in range(13):
                dp[k] += dp_tmp_roll[k]
    else:
        dp_tmp_roll = rotate(dp_tmp,int(s)*mul%mod)
        for k in range(13):
            dp[k] += dp_tmp_roll[k]
    for n in range(13):
        dp[n] = dp[n]%(10**9+7)
    dp_tmp = dp
    mul = mul*10%13
print(dp[amari])

Submission status: Time Limit Exceeded

Solution code:
S = input()
mod = 13
amari = 5
import numpy as np
dp_temp = np.zeros((mod),dtype="uint64")
dp_temp[0] = 1

def nadd(x_array,y_array,i,mod):
    for n in range(10):
        y_array += np.roll(x_array,n*(10**i)%mod)
    return y_array


for i,s in enumerate(S[::-1]):
    if s == "?":
        dp = np.zeros((mod),dtype="uint64")
        dp = nadd(dp_temp,dp,i,mod)
    else:
        dp = np.roll(dp_temp,int(s)*(10**i)%mod)
    dp = dp%(10**9+7)
    dp_temp = dp
print(dp[amari])

Submission status: Time Limit Exceeded

Solution code:
s = input()
a = [[0 for i in range(len(s))] for j in range(13)]

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


for i in range(len(s)-1):
    if s[i+1] == '?':
        for j in range(13):
            #a[j][i]
            tmp = j * 10
            for k in range(10):
                a[tmp%13][i+1] += a[j][i]
                tmp += 1
    else:
        tmp = int(s[i+1])
        for j in range(13):
            x = (j * 10 + tmp)%13
            a[x][i+1] += a[j][i]
#print(a)
print(a[5][len(s)-1]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
rotate = lambda x,y: x[-y:] + x[:-y]
S = input()
mod = 13
amari = 5
dp_tmp = [0]*13
dp_tmp[0] = 1
for i,s in enumerate(S[::-1]):
    dp = [0]*13
    if s == "?":
        for n in range(10):
            dp_tmp_roll = rotate(dp_tmp,n*(10**i)%mod)
            for k in range(13):
                dp[k] += dp_tmp_roll[k]
    else:
        dp_tmp_roll = rotate(dp_tmp,int(s)*(10**i)%mod)
        for k in range(13):
            dp[k] += dp_tmp_roll[k]
    for n in range(13):
        dp[n] = dp[n]%(10**9+7)
    dp_tmp = deepcopy(dp)
print(dp[amari])

Submission status: Time Limit Exceeded

Solution code:
S = input()
mod = 13
amari = 5

import numpy as np
dp = np.zeros((len(S)+1,mod),dtype="uint64")
dp[0,0%mod] = 1
for i,s in enumerate(S[::-1]):
    if s == "?":
        for n in range(10):
            dp[i+1,:] += np.roll(dp[i],n*(10**i)%mod)
    else:
        dp[i+1,:] += np.roll(dp[i],int(s)*(10**i)%mod)
    dp = dp%(10**9+7)
print(dp[-1,amari])

Submission status: Time Limit Exceeded

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


main()

Submission status: Time Limit Exceeded

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


main()