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: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

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


s = ns()
n = len(s)

TEN = 10
THIRTEEN = 13
MOD = 10**9 + 7
dp = [[0]*THIRTEEN for _ in range(n+1)]
dp[0][0] = 1

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

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

print(dp[n][5])

Submission status: Accepted

Solution code:
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac
import bisect
import heapq

import logging
logging.basicConfig(level=logging.DEBUG)

import sys
input = sys.stdin.readline().rstrip

setrecursionlimit(1000000)

MOD = 10**9+7
INF = float('inf')

def main():
    S=input()

    dp = [[0] * 13 for _ in range(len(S)+1)] # 0の行＋桁数
    dp[0][0]=1
    for k in range(len(S)):
        c=S[k]
        #print(c)
        if c=="?":
            for i in range(13):
                for j in range(10):
                    dp[k+1][(i*10+j)%13]+=dp[k][i]
                    dp[k+1][(i*10+j)%13]%=MOD
        else:
            for i in range(13):
                dp[k+1][(i*10+int(c))%13]+=dp[k][i]
                dp[k+1][(i*10+int(c))%13]%=MOD
    #print(dp)
    print(dp[len(S)][5])

main()

Submission status: Accepted

Solution code:
s = input()
ans,mod = [0]*13,10**9+7
if s[0]=="?": ans = [1]*10+[0]*3
else: ans[int(s[0])] = 1
for i in s[1:]:
    dp = [0]*13
    for j in range(13): dp[j*10%13] = ans[j]%mod
    dp+=dp
    if i=="?":
        for j in range(13): ans[j] = sum(dp[j+4:j+14])
    else:
        for j in range(13): ans[j] = dp[j+13-int(i)]
print(ans[5]%mod)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

def main():
    s = [int(in_i) if in_i != '?' else -1 for in_i in list(open(0).read())[:-1]]
    n = len(s)

    cnt = [0] * 13
    if s[0] == -1:
        for j in range(10):
           cnt[j] = 1
    else:
        cnt[s[0]] = 1

    for cur_s in s[1:]:
        dp = [0] * 26
        for i in range(13):
            dp[i*10%13] = cnt[i] % MOD
        dp[13:] = dp[:13]

        if cur_s == -1:
            for i in range(13):
                cnt[i] = sum(dp[i+4:i+14])
        else:
            for i in range(13):
                cnt[i] = dp[i+13-cur_s]

    ans = cnt[5] % MOD
    print(ans)
    return()

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S = input()

rs = [0] * 13

M = 10**9 + 7

if S[-1] == "?":
    rs[:10] = [1] * 10
else:
    rs[int(S[-1])] = 1

for i in range(1, len(S)):
    nrs = [0] * 13
    c = S[-i - 1]
    if c == "?":
        ns = range(10)
    else:
        ns = [int(c)]
    for n in ns:
        r = (10 ** (i % 6)) * n % 13
        for j in range(13):
            jj = (j + r) % 13
            nrs[jj] = (nrs[jj] + rs[j]) % M
    rs = nrs

# print(rs)
print(rs[5])

Submission status: Accepted

Solution code:
MOD = 1000000007
s = [int(x) if x!="?" else -1 for x in input()]
dp = [[0] *  13 for _ in range(len(s))] 

if s[0] == -1:
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(s[0])] = 1
 
table = [ s % 13 for s in range(130)]
for index in range(1, len(s)):
    if not s[index] == -1:
        value = int(s[index])
 
        for old_amari in range(13):
            new_amari = (table[old_amari * 10] + value) % 13
            dp[index][new_amari] += dp[index-1][old_amari]
    else:
        for value in range(10):
            for old_amari in range(13):
                new_amari = (table[old_amari * 10] + value) % 13
                dp[index][new_amari] += dp[index - 1][old_amari]
 
    for i in range(len(dp[index])):
        dp[index][i] %= MOD

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

Submission status: Accepted

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    s = [int(i) if i != "?" else -1 for i in list(str(input().rstrip('\n')))]
    ls = [[0] * 13 for _ in range(len(s))]
    mod = 10 ** 9 + 7
    for i in range(1):
        if s[-i-1] != -1:
            ls[i][s[-i-1] % 13] = 1
        else:
            for j in range(10):
                ls[i][j % 13] = 1
    for i in range(1, len(s)):
        mult = pow(10, i, 13)
        if s[-i-1] == -1:
            for j in range(10):
                for k in range(13):
                    ls[i][(mult * j + k) % 13] += ls[i-1][k]
                    ls[i][(mult * j + k) % 13] %= mod
        else:
            for k in range(13):
                ls[i][(mult * s[-i-1] + k) % 13] += ls[i-1][k]
                ls[i][(mult * s[-i-1] + k) % 13] %= mod
    print(ls[-1][5])


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
def main():
    MOD = 7 + 10**9
    S = tuple(input())
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] += 1
    s=[1]
    for n in range(1,N):
        s.append((s[n-1]*10)%13)
    for i in range(N):
        for k in range(13):
            if S[-(i+1)] != '?':
                dp[i+1][(k+int(S[-(i+1)])*s[i])%13] += dp[i][k] 
                dp[i+1][(k+int(S[-(i+1)])*s[i])%13] %= MOD
            else:
                for l in range(10):
                    dp[i+1][(k+l*s[i])%13] += dp[i][k]
                    dp[i+1][(k+l*s[i])%13] %= MOD
    print(dp[-1][5])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
MOD=10**9+7

S=[int(x) if x != "?" else -1 for x in input()]
N=len(S)

#現在考えてる1つ前の桁数で, 余りがiになる整数の個数
r=[0]*13

#まず1つ目の値が1の位とする
s=S[0]
if s != -1:
  r[s] = 1
else:
  for i in range(10):
    r[i] = 1

#桁を進めながら個数をカウント
for i in range(1,N):
  #dp[j]
  #現在考えている桁(i)を除く, 余りがjとなる整数の個数
  dp = [0]*26
  #桁が1つ上がるので, 1つ前のあまりが10倍になる
  for j in range(13):
    dp[j*10%13] += r[j] % MOD
  #アクセスを高速にするため2倍の長さをとる(dp[i]==di[i+13])
  dp[13:26] = dp[0:13]
  r=[0]*13
  s=S[i]
  if s == -1:
    w=sum(dp[4:14])
    for j in range(13):
      r[j] += w
      w += dp[j+1] -dp[j+4]
  else:
    for j in range(13):
      r[j] += dp[13-s+j]
print(r[5]%MOD)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
def dp(a):
    L = len(a)

    dp = [[0 for j in range(13)] for k in range(L + 1)]
    dp[0][0] = 1
    for i in range(L):
        if a[i] == "?":
            for j in range(10):
                for k in range(13):
                    dp[i + 1][(j + k*10) % 13] += dp[i][k]
                    dp[i + 1][(j + k*10) % 13] %= MOD
        else:
            for k in range(13):
                dp[i + 1][(int(a[i])+k*10) % 13] += dp[i][k]
                dp[i + 1][(int(a[i])+k*10) % 13] %= MOD
    print(dp[L][5] % MOD)


def main():
    S = input()
    dp(S)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
def dp(a):
    L = len(a)

    dp = [[0 for j in range(13)] for k in range(L + 1)]
    dp[0][0] = 1
    for i in range(L):
        if a[i] == "?":
            for j in range(10):
                for k in range(13):
                    dp[i + 1][(j + k*10) % 13] += dp[i][k]
                    dp[i + 1][(j + k*10) % 13] %= MOD
        else:
            for j in range(13):
                dp[i + 1][(int(a[i])+j*10) % 13] += dp[i][j]
                dp[i + 1][(int(a[i])+j*10) % 13] %= MOD
    print(dp[L][5] % MOD)


def main():
    S = input()
    dp(S)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
r = [[(j - k) * 9 % 13 for j in range(10)] for k in range(13)]
d = [1] + [0] * 12
M = 10 ** 9 + 7
for c in input():
    if c == '?':
        d = [sum(d[j] for j in k) % M for k in r]
    else:
        d = [d[(int(c) - k) * 9 % 13] for k in range(13)]
    #print(d)
print(d[5])

Submission status: Accepted

Solution code:
S = input()
 
MOD = 10**9+7
 
dp = [[0]*13 for _ in range(len(S) + 1)]
 
 
dp[0][0] = 1
 
mul = 1
for index in range(len(S)):
    s = S[len(S) - index - 1]
    if s == '?':
        for pre_index in range(13):
            for i in range(10):
                next_i = (i * mul +  pre_index ) % 13
                dp[index+1][next_i] += dp[index][pre_index] 
                dp[index+1][next_i] %= MOD

    else:
        for pre_index in range(13):
            i = int(s)
            next_i = (i * mul  +  pre_index ) % 13
            dp[index+1][next_i] += dp[index][pre_index] 
            dp[index+1][next_i] %= MOD
    mul *= 10
    mul %= 13
 
 
 
print(dp[len(S)][5])

Submission status: Accepted

Solution code:
S = input()
 
MOD = 10**9+7
 
dp = [[0]*13 for _ in range(len(S) + 1)]
 
 
dp[0][0] = 1
 
for index in range(len(S)):
    s = S[index]
    if s == '?':
        for pre_index in range(13):
            for i in range(10):
                next_i = (i +  pre_index * 10 ) % 13
                dp[index+1][next_i] += dp[index][pre_index] 
                dp[index+1][next_i] %= MOD

    else:
        for pre_index in range(13):
            i = int(s)
            next_i = (i +  pre_index  * 10) % 13
            dp[index+1][next_i] += dp[index][pre_index] 
            dp[index+1][next_i] %= MOD
 
 
 
print(dp[len(S)][5])

Submission status: Accepted

Solution code:
S = input()
 
MOD = 10**9+7
 
dp = [[0]*13 for _ in range(len(S) + 1)]
 
 
dp[0][0] = 1
 
for index in range(len(S)):
    if S[index] == '?':
        for pre_index in range(13):
            for i in range(10):
                next_i = (i +  pre_index * 10 ) % 13
                dp[index+1][next_i] += dp[index][pre_index] 
                dp[index+1][next_i] %= MOD

    else:
        for pre_index in range(13):
            i = int(S[index])
            next_i = (i +  pre_index  * 10) % 13
            dp[index+1][next_i] += dp[index][pre_index] 
            dp[index+1][next_i] %= MOD
 
 
 
print(dp[len(S)][5])

Submission status: Accepted

Solution code:
MOD=1000000007
S=input()[::-1]
N=len(S)
pows=list(range(10))
dp=[[0]*13 for _ in range(N+1)]
dp[0][0]=1
for i in range(N):
    for src in range(13):
        for j,p in enumerate(pows):
            if S[i]=='?' or int(S[i])==j:
                dst = (src+p)%13
                dp[i+1][dst] = (dp[i+1][dst]+dp[i][src])%MOD
    for i in range(10):
        pows[i]=(pows[i]*10)%13
print(dp[N][5])

Submission status: Accepted

Solution code:
S = input()

length = len(S)
dp = [[0] * 13 for _ in range(length + 1)]
dp[0][0] = 1
mul = 1
INF = 10 ** 9 + 7

for i in range(length):
    
    x = S[- (i + 1)]
    
    if x == "?":
        
        for j in range(13):
            
            for k in range(10):
            
                dp[i + 1][(k * mul + j) % 13] += dp[i][j]
                dp[i + 1][(k * mul + j) % 13] %= INF
                
    else:
        
        c = int(x)
        
        for j in range(13):
            
            dp[i + 1][(c * mul + j) % 13] += dp[i][j]
            dp[i + 1][(c * mul + j) % 13] %= INF
            
    mul = (mul * 10) % 13
    
print(dp[length][5])

Submission status: Accepted

Solution code:
S = list(input())
dp = [[0 for _ in range(13)] for _ in range(len(S)+1)]
dp[0][0]=1
#print(dp[15][5])
for i in range(len(S)):
  a = 0
  if S[i]=="?":
    a = -1
  else:
    a = int(S[i])
  for j in range(10):
    if a!=-1 and a!=j:
      continue
    for k in range(13):
      dp[i+1][(k*10+j)%13] += dp[i][k]
  for k in range(13):
    dp[i+1][k] %=(10**9+7)
print(dp[len(S)][5])

Submission status: Accepted

Solution code:
S = list(input())
dp = [[0 for _ in range(13)] for _ in range(len(S)+1)]
dp[0][0]=1
#print(dp[15][5])
for i in range(len(S)):
  a = 0
  if S[i]=="?":
    for j in range(10):
      for k in range(13):
        dp[i+1][(k*10+j)%13] += dp[i][k]
  else:
    a = int(S[i])
    for k in range(13):
      dp[i+1][(k*10+a)%13] += dp[i][k]
  for k in range(13):
    dp[i + 1][k] %= (10**9+7)
print(dp[len(S)][5])

Submission status: Accepted

Solution code:
s = input()
pre = [1]+[0]*12
n = 10**9 + 7
tem = [[i*j%13 for i in range(10)] for j in range(13)]
t = 1
for i in range(len(s)):
    if s[-1*i-1] > "9":
        pre = [sum([pre[k-i] for i in tem[t]])%n for k in range(13)]      
    else:
        te = int(s[-1*i-1])*t % 13
        pre = [pre[i-te] for i in range(13)]
    t = t*10 % 13
print(pre[5])

Submission status: Accepted

Solution code:
def main():
  s = input()
  divisor = 10 ** 9 + 7
  dp = [[0] * 13 for _ in range(len(s) + 1)]
  dp[0][0] = 1
  lut = [i % 13 for i in range(130)]
  list10 = list(range(10))
  list13 = list(range(13))
  for i in range(len(s)):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    if s[i] == '?':
      j10 = 0
      for j in list13:
        dpij = dpi[j]
        for k in list10:
          dpi1[lut[j10 + k]] += dpij
        j10 += 10
    else:
      t = int(s[i])
      for j in list13:
        dpi1[t] += dpi[j]
        t = lut[t + 10]
    for k in list13:
      dpi1[k] %= divisor
  print(dp[len(s)][5])
main()

Submission status: Accepted

Solution code:
def main():
  s = input()
  divisor = 10 ** 9 + 7
  dp = [[0] * 13 for _ in range(len(s) + 1)]
  dp[0][0] = 1
  lut = [i % 13 for i in range(130)]
  list10 = list(range(10))
  for i in range(len(s)):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    if s[i] == '?':
      j10 = 0
      for j in range(13):
        dpij = dpi[j]
        for k in list10:
          dpi1[lut[j10 + k]] += dpij
        j10 += 10
    else:
      t = int(s[i])
      for j in range(13):
        dpi1[lut[t]] += dpi[j]
        t += 10
    for k in range(13):
      dp[i + 1][k] %= divisor
  print(dp[len(s)][5])
main()

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

S = input()
L = len(S)
memo = [[0 for i in range(14)] for j in range(L + 1)]
dp = [[0 for i in range(14)] for j in range(L + 1)]

dp[0][0] = 1

for k in range(L):
    for m in range(13):
        if S[k] == '?':
            for i in range(10):
                dp[k + 1][(m * 10 + i) % 13] += dp[k][m]
        else:
            dp[k + 1][(m * 10 + int(S[k])) % 13] += dp[k][m]

        for i in range(13):
            dp[k+1][i] %= MOD

print(dp[L][5])

Submission status: Accepted

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

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

for i in range(n):
    if s[i] == '?':
        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

res = dp[n][5]
print(res)

Submission status: Accepted

Solution code:
import numpy as np
MOD = 10 ** 9 + 7

S = [int(x) if x != "?" else -1 for x in input()]
N = len(S)

# 現在考えてる一つ前の桁数で、余りが i になる整数の個数
r = [0]*13

# まず一つ目の値が１の位とする
s = S[0]
if s != -1:
  r[s] = 1
else:
  for i in range(10):
    r[i] = 1

# 桁を進めながら個数をカウント
for i in range(1, N):
    # dp[j]
    # 現在考えている桁(i)を除く、余りが j となる整数の個数
    dp = [0]*26
    # 桁が一つ上がるので、一つ前の余りが 10 倍になる
    for j in range(13):
      dp[j*10%13] += r[j] % MOD
    # アクセスを高速にするため２倍の長さとる (dp[i] == dp[i + 13])
    dp[13:26] = dp[0:13]
    r = [0]*13
    s = S[i]
    if s == -1:
      w = sum(dp[4:14])
      for j in range(13):
        r[j] += w
        w += dp[j+1] -dp[j+4]
    else:
      for j in range(13):
        r[j] += dp[13-s+j]
print(r[5]%MOD)

Submission status: Accepted

Solution code:
S = input()

INF = 10 ** 9 + 7

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

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

Submission status: Accepted

Solution code:
from sys import exit, stderr, stdin
input = stdin.readline


def main():
    MOD = 10**9 + 7
    S = input()[:-1]
    L = len(S)
    # 余り
    memo = [0 for _ in range(13)]
    memo[0] = 1

    for i in range(L):
        memo_prev = [x for x in memo]
        memo = [0 for _ in range(13)]
        # 数字なら以前までの余りにたす
        if S[i].isnumeric():
            n = int(S[i])
            for m in range(13):
                cur = (10*m+n)%13
                memo[cur] += memo_prev[m]
        # ?なら1~10の余りのケース全てをためす
        else:
            for n in range(10):
                for m in range(13):
                    cur = (10*m+n)%13
                    memo[cur] += memo_prev[m]
            for m in range(13):
                memo[m] %= MOD
    print(memo[5])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

for s in S:
    prev = [x for x in dp]
    dp = [0] * 13
    if s == '?':
        add = range(10)
    else:
        add = [int(s)]
    for i in range(13):
        for a in add:
            dp[(10*i+a)%13] += prev[i]
    dp = [x%MOD for x in dp]
print(dp[5])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate
import sys


def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


def main():
    s = S().strip()
    dp = [0] * 13
    dp[0] = 1
    trans_list = [i * 10 % 13 for i in range(13)]
    for i in s:
        nxt_dp = [0] * 13
        for j in range(13):
            if i == '?':
                for k in range(10):
                    nxt_dp[(trans_list[j] + k) % 13] += dp[j]
                    nxt_dp[(trans_list[j] + k) % 13] %= mod
            else:
                nxt_dp[(trans_list[j] + int(i)) % 13] += dp[j]
                nxt_dp[(trans_list[j] + int(i)) % 13] %= mod
        dp = nxt_dp

    return dp[5]


print(main())

Submission status: Accepted

Solution code:
def main():
  s = input()[::-1]
  multiplier = 1
  divisor = 10 ** 9 + 7
  list10 = list(range(10))
  list13 = list(range(13))
  p = [0] * 13
  np = [0] * 13
  rt = [i % 13 for i in range(121)]
  p[0] = 1
  for i in range(len(s)):
    if s[i] != '?':
      r = rt[int(s[i]) * multiplier]
      for j in list13:
        np[rt[j + r]] = p[j]
    else:
      r = 0
      for j in list10:
        for k in list13:
          np[rt[k + r]] += p[k]
        r = rt[r + multiplier]
    for j in list13:
      p[j] = np[j] % divisor
      np[j] = 0
    multiplier = rt[10 * multiplier]
  print(p[5])
main()

Submission status: Accepted

Solution code:

s = input()
n = len(s)
dp1 =[0 for _ in range(13)]
dp1[0]=1


move = [[] for _ in range(13)]

for i in range(10):
    for j in range(13):
        move[(10*j+i)%13].append(j)



for i in range(n):
    dp2 =[0 for _ in range(13)]
    if s[i]=="?":
        si = range(10)
        for mod,ex in enumerate(move):
            dp2[mod] += sum([dp1[x] for x in ex])
    else:
        si = int(s[i])
        for j in range(13):
            dp2[(10*j+si)%13]+=dp1[j]
    dp1 = [x%(10**9+7) for x in dp2] 


print(dp1[5])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque, Counter as cnt

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]
def nlist(n, v):
    if not n: return v.copy()
    return [nlist(n[1:], v) for _ in range(n[0])]

class mod:
    def __init__(self, v=0):
        self.v = v
        self.v %= MOD
    def __add__(self, v):
        self.v += v.v
        self.v %= MOD
        return self
    def __str__(self):
        return str(self.v)

# エントリーポイント
def main():
    S = input(str)
    dp = [[mod(0) for _ in range(13)] for _ in range(len(S) + 1)]
    dp[0][0].v = 1
    for i, s in enumerate(S):
        i += 1
        loop = range(10) if s == "?" else [int(s)]
        for n in range(13):
            for m in loop:
                dp[i][(n * 10 + m) % 13] += dp[i - 1][n]
                # dp[i][(n * 10 + m) % 13] %= MOD
    print(dp[-1][5])

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque, Counter as cnt

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]
def nlist(n, v):
    if not n: return v.copy()
    return [nlist(n[1:], v) for _ in range(n[0])]

class mod:
    def __init__(self, v=0):
        self.v = v
        self.v %= MOD
    def __add__(self, v):
        self.v += int(v)
        self.v %= MOD
        return self
    def __sub__(self, v):
        self.v -= int(v)
        return self
    def __mul__(self, v):
        self.v *= int(v)
        self.v %= MOD
        return self
    def __int__(self):
        return int(self.v)
    def __str__(self):
        return str(self.v)

# エントリーポイント
def main():
    S = input(str)
    dp = [[0 for _ in range(13)] for _ in range(len(S) + 1)]
    dp[0][0] = 1
    for i, s in enumerate(S):
        i += 1
        loop = range(10) if s == "?" else [int(s)]
        for n in range(13):
            for m in loop:
                dp[i][(n * 10 + m) % 13] += dp[i - 1][n]
                dp[i][(n * 10 + m) % 13] %= MOD
    print(dp[-1][5])

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque, Counter as cnt

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]
def nlist(n, v):
    if not n: return v.copy()
    return [nlist(n[1:], v) for _ in range(n[0])]

class mod:
    def __init__(self, v=0):
        self.v = v
        self.v %= MOD
    def __add__(self, v):
        self.v += int(v)
        self.v %= MOD
        return self
    def __sub__(self, v):
        self.v -= int(v)
        return self
    def __mul__(self, v):
        self.v *= int(v)
        self.v %= MOD
        return self
    def __int__(self):
        return int(self.v)
    def __str__(self):
        return str(self.v)

# エントリーポイント
def main():
    S = input(str)
    dp = [[mod(0) for _ in range(13)] for _ in range(len(S) + 1)]
    dp[0][0].v = 1
    for i, s in enumerate(S):
        i += 1
        loop = range(10) if s == "?" else [int(s)]
        for n in range(13):
            for m in loop:
                dp[i][(n * 10 + m) % 13] += dp[i - 1][n]
    print(dp[-1][5])

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()

Submission status: Accepted

Solution code:
mod=10**9+7
r=[[(j-k)*9%13 for j in range(10)] for k in range(13)]
dp=[1]+[0]*12
for c in input():
  dp = [sum(dp[j] for j in k)%mod for k in r] if c>'9' else [dp[(int(c)-k)*9%13] for k in range(13)]
print(dp[5])

Submission status: Accepted

Solution code:
import math
from collections import defaultdict

mod = pow(10, 9)+7

def digits_parade(strr, n):
	dp = [[0]*13 for i in range(n)]
	if strr[0]=="?":
		for k in range(10):
			dp[0][k] = 1
	else:
		dp[0][int(strr[0])] = 1

	for i in range(1, n):
		if strr[i]=="?":
			for j in range(10):
				temp = j
				for k in range(13):
					dp[i][(10*k + temp)%13] += dp[i-1][k]
					dp[i][(10*k + temp)%13] %= mod
		else:
			temp = int(strr[i])
			for k in range(13):
				dp[i][(10*k + temp)%13] += dp[i-1][k]
				dp[i][(10*k + temp)%13] %= mod
	return dp[n-1][5]

strr = input()
n = len(strr)

ans =digits_parade(strr, n)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
s = input()
effects = [1, 10, 9, 12, 3, 4]
mod = 10**9+7

amari = np.array([1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
arrays = [np.eye(13, k=i, dtype=np.int64)+np.eye(13, k=i-13, dtype=np.int64) for i in range(13)]
brrays = [sum(arrays[c*effects[i]%13] for c in range(10)) for i in range(6)]
for i, c in enumerate(reversed(s)) :
    if c != "?" :
        c = int(c)
        array = arrays[c*effects[i%6]%13]
        amari = np.dot(amari, array)
    else :
        array = brrays[i%6]
        amari = np.dot(amari, array)%mod

print(amari[5])

Submission status: Accepted

Solution code:
s=input()[::-1]
p=[1]+[0]*12
q=1
t=[[(i*k)%13 for i in range(10)]for k in range(13)]
for i in s:
    if i!="?":
        i=int(i)
        g=t[q][i]
        p=p[-g:]+p[:-g]
    else:
        d=[0]*13
        for j in t[q]:
            r=p[-j:]+p[:-j]
            d=[(r[i]+d[i])%(10**9+7)for i in range(13)]
        p=d
    q=(q*10)%13
print(p[5]%(10**9+7))

Submission status: Accepted

Solution code:
s=input()[::-1]
p=[1]+[0]*12
q=1
t=[[(i*k)%13 for i in range(10)]for k in range(13)]
for i in s:
    if i!="?":
        i=int(i)
        g=t[q][i]
        p=p[-g:]+p[:-g]
    else:
        d=[0]*13
        for j in t[q]:
            r=p[-j:]+p[:-j]
            d=[(r[i]+d[i])%(10**9+7)for i in range(13)]
        p=d
    q=(q*10)%13
print(p[5]%(10**9+7))

Submission status: Accepted

Solution code:
s=input()
n=len(s)
dp=[[0]*13 for _ in range(100010)]
dp[0][0]=1
for i in range(n):
    for j in range(10):
        if s[i]==str(j) or s[i]=="?":
            for h in range(13):
                dp[i+1][(h*10+j)%13]+=dp[i][h]
    for h in range(13):
        dp[i+1][h]%=1000000007
print(dp[n][5])

Submission status: Accepted

Solution code:
S = str(input())

# dpテーブルを定義する[桁数][余りの数]

dp = [[0]*13 for _ in range(100001)]

# dpテーブルの初期条件, 0桁の数字を13で割って0余るパターンが1通りあるとして計算をしていく
dp[0][0] = 1

for i in range(len(S)):
    # 「(i-1)文字目まで計算した結果、余りがjになるようなものはk通りある」ということをメモして、
    # そのk通りがi文字目の計算をしたときにどのjに遷移するかを求めて行く
    for remain in range(13):  # それぞれの余りのパターンの総数について
        # S[i]の取り方について全通り試して行く
        if S[i] == '?':  # 今見ている数字が'?'である場合
            for target in range(10):  # 0~9まで試す
                next_remain = (remain*10 + target) % 13
                dp[i+1][next_remain] += dp[i][remain]
                dp[i+1][next_remain] %= 1000000007
        else:
            next_remain = (remain*10 + int(S[i])) % 13
            dp[i+1][next_remain] += dp[i][remain]
            dp[i+1][next_remain] %= 1000000007

# print(dp[0])
# print(dp[1])
print(dp[len(S)][5])

Submission status: Accepted

Solution code:
S = str(input())

dp = [[0]*13 for _ in range(100001)]  # [桁数][あまりの数] = 個数

dp[0][0] = 1

for i in range(len(S)):  # Sへのアクセスは0-index
    for remain in range(13):  # あまりのパターン
        if S[i] == '?':
            for j in range(10):  # ?の取り方を全通り試す
                next_remain = (remain*10 + j) % 13
                # dpの遷移
                dp[i+1][next_remain] += dp[i][remain]
                dp[i+1][next_remain] %= 1000000007
        else:  # 今見ている桁が?ではなく数字であれば
            next_remain = (remain*10 + int(S[i])) % 13
            # dpの遷移
            dp[i+1][next_remain] += dp[i][remain]
            dp[i+1][next_remain] %= 1000000007

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

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
 
s = str(input())
 
s = list(s)
 
cur = [0] * 13
 
if s[0] != "?":
    cur[int(s[0])] = 1
else:
    for j in range(10):
        cur[j] = 1
 
for i in range(1,len(s)):
    pre = cur[:]
    cur = [0] * 13
    if s[i] != "?":
        for j in range(13):
            q = (j * 10 + int(s[i])) % 13
            cur[q] += pre[j] % MOD
    else:
        for j in range(13):
            for k in range(10):
                p = (j * 10 + k) % 13
                cur[p] += pre[j] % MOD
 
print(cur[5] % MOD)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

s = str(input())

s = list(s)

cur = [0] * 13

if s[0] != "?":
    cur[int(s[0])] = 1
else:
    for j in range(10):
        cur[j] = 1

for i in range(1,len(s)):
    pre = cur[:]
    cur = [0] * 13
    if s[i] != "?":
        for j in range(13):
            q = (j * 10 + int(s[i])) % 13
            cur[q] += pre[j] % MOD
    else:
        for j in range(13):
            for k in range(10):
                p = (j * 10 + k) % 13
                cur[p] += pre[j] % MOD

print(cur[5] % MOD)

Submission status: Accepted

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