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:
S = str(input())

# 桁数
N = len(S)
MOD = 10**9 + 7

# dp[i][j] := Sの上からi桁目までを考えた時、それを13で割った余りがjになる方法の数
dp = [[0 for _ in range(13)]for _ in range(N + 1)]

# １桁目について
if S[0] == "?":
    # ?に0, 1, ..., 9を入れることができる
    for i in range(10):
        dp[1][i] = 1
else:
    dp[1][int(S[0])] = 1

# 1, 2, ..., N-1桁から、
# 2, 3, ..., N桁についての遷移を考える
for i in range(1, N):
    for j in range(13):
        if S[i] == "?":
            for k in range(10):
                dp[i + 1][(j * 10 + k) % 13] += dp[i][j]
                dp[i + 1][(j * 10 + k) % 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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

S = input()

dp = [0] * 13

dp[0] = 1

l = len(S)

for i in S:
    nextdp = [0] * 13
    if i == "?":
        for k in range(10):
            for j in range(13):
                nextdp[((j * 10) + k) % 13] += dp[j]
                # nextdp[((j * 10) + k) % 13] %= mod

    else:
        k = int(i)
        for j in range(13):
            nextdp[((j * 10) + k) % 13] += dp[j]
            # nextdp[((j * 10) + k) % 13] %= mod

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

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

print(dp[5])

Submission status: Accepted

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

Submission status: Accepted

Solution code:


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    S=input()
    N=len(S)
    
    dp=[[0]*13 for _ in range(N+1)]
    dp[0][0]=1
    
    for i in range(N):
        s=S[i]
        
        for j in range(13):
            temp=dp[i][j]
            if s!="?":
                a=int(s)
                nxt=(j*10+a)%13
                dp[i+1][nxt]+=temp
                
            else:
                for k in range(10):# ?=0~9
                    nxt=(j*10+k)%13
                    dp[i+1][nxt]=(dp[i+1][nxt]+temp)%mod
                    
    print(dp[-1][5])
    
    # for i in range(N+1):
    #     print(dp[i])

main()

Submission status: Accepted

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))


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

Submission status: Accepted

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

# dp[i][j]: i桁目までで，余りがjになるものの場合の数 
dp = [[0]*13 for _ in range(len(S)+1)]
dp[0][0] = 1

for i in range(len(S)):
    pow10 = pow(10,i,13)
    if S[i] != '?':
        d = int(S[i])
        for r in range(13):
            dp[i+1][(r + d*pow10) % 13] = dp[i][r]
    else:
        for d in range(10):
            for r in range(13):
                dp[i+1][(r + d*pow10) % 13] += dp[i][r]
                dp[i+1][(r + d*pow10) % 13] %= MOD

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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

S = list(input())[::-1]
leng = len(S)
mod = 10**9+7

old_dp = [0]*13
old_dp[0] = 1

for i in range(leng):
    dp = [0]*13
    if S[i]!='?':
        d = int(S[i])
        d = d*pow(10, i, 13)
        for j in range(13):
            dp[j] += old_dp[(j-d)%13]
            dp[j] %= mod
    else:
        for d in range(10):
            d = d*pow(10, i, 13)
            for j in range(13):
                dp[j] += old_dp[(j-d)%13]
                dp[j] %= mod
    old_dp = dp

print(dp[5])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod = 1000000007
    
S = list(input())

n = len(S)

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

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

Submission status: Accepted

Solution code:
S = str(input()); N = len(S)
S = list(S); S.reverse() #1桁目からに変換
MOD = pow(10,9)+7
dp = [0 for _ in range(13)] #13で割ってi余る個数
dp[0] = 1
keta = 1
for i in range(N):
  p = [0 for _ in range(13)]
  dp,p = p,dp #dpが次。pが一個前。
  if i != 0:
    keta = (keta*10)%13
  if S[i] == "?":
    for x in range(10):
      amari = x*keta%13
      for j in range(13):
        if j >= amari:
          mae = j-amari
        else:
          mae = j-amari+13
        dp[j] += p[mae]%MOD
  else:
    amari = int(S[i])*keta%13
    for j in range(13):
      if j >= amari:
        mae = j-amari
      else:
        mae = j-amari+13
      dp[j] += p[mae]%MOD
#print(dp)
print(dp[5]%MOD)

Submission status: Accepted

Solution code:
S = input()
N = len(S)
m = 10**9 + 7

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

for i in range(N):
    p = pow(10,i,13)
    for j in range(13):
        digit = S[N-1-i]
        if digit == '?':
            for k in range(10):
                d = (j+k*p%13)%13
                dp[d][i+1] += dp[j][i]
                dp[d][i+1] %= m

        else:
            k = int(digit)
            d = (j+k*p%13)%13
            dp[d][i+1] += dp[j][i]
            dp[d][i+1] %= m
print(dp[5][N])

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):
    si = s[i]
    if si == '?':
        for j in range(13):
            for k in range(10):
                dp[i+1][(j*10+k)%13] += dp[i][j]
                dp[i+1][(j*10+k)%13]%=MOD

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


print(dp[n][5])

Submission status: Accepted

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

dp=[[0]*13 for i in range(len(s)+1)]
dp[0][0]=1

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

Submission status: Accepted

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

# ある余りを10倍して13で割ったときの余りへの変換表
rests = [0] * 13
for i in range(len(rests)):
  rests[i] = i * 10 % 13
  
dp = [[0] * 13 for i in range(len(S))]

x0 = S[0]
if x0 != "?":
  dp[0][int(x0)] = 1
else:
  # ?の場合は0～9を全て取ることができ、その余りは0～9となる
  for i in range(10):
    dp[0][i] = 1

for i in range(1, len(dp)):
  x = S[i]
  if x != "?":
    x = int(x)
    # ?じゃない場合は、直前の各あまりをrestsで変換して、その数を足したところに数を代入する
    for j in range(len(dp[i - 1])):
      dp[i][(rests[j] + x) % 13] += dp[i - 1][j]
      dp[i][(rests[j] + x) % 13] %= MOD
  else:
    # ?は0～9の全てを取ることができる
    for j in range(len(dp[i - 1])):
      for k in range(10):
        dp[i][(rests[j] + k) % 13] += dp[i - 1][j]
        dp[i][(rests[j] + k) % 13] %= MOD
  
print(dp[-1][5])

Submission status: Accepted

Solution code:
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline

P = 10 ** 9 + 7
Q = 13


@nb.njit("i8(i8[:])", cache=True)
def solve(S):
    N = len(S)
    dp = np.zeros(shape=(N + 1, Q), dtype=np.int64)
    dp[0][0] = 1
    for i in range(N):
        D = S[i]
        if D == -1:
            for d in range(10):
                for j in range(Q):
                    dp[i + 1][(10 * j + d) % Q] += dp[i][j]
        else:
            for j in range(Q):
                dp[i + 1][(10 * j + D) % Q] += dp[i][j]

        for j in range(Q):
            dp[i + 1][j] %= P

    return dp[N][5]


def main():
    S = input().rstrip()

    S = np.array([int(s) if s != "?" else -1 for s in S], dtype=np.int64)
    ans = solve(S)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline

P = 10 ** 9 + 7
Q = 13


@nb.njit("i8(i8[:])", cache=True)
def solve(S):
    N = len(S)
    dp = [[0] * Q for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(N):
        D = S[i]
        if D == -1:
            for d in range(10):
                for j in range(Q):
                    dp[i + 1][(10 * j + d) % Q] += dp[i][j]
        else:
            d = int(D)
            for j in range(Q):
                dp[i + 1][(10 * j + d) % Q] += dp[i][j]

        for j in range(Q):
            dp[i + 1][j] %= P

    return dp[N][5]


def main():
    S = input().rstrip()

    S = np.array([int(s) if s != "?" else -1 for s in S], dtype=np.int64)
    ans = solve(S)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
s = list(input())

MOD = pow(10, 9) + 7

n = len(s)

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

#r = list(range(10))

#init
if s[-1] == "?":
    for j in range(10):
        dp[0][j] = 1
else:
    q = int(s[-1])
    dp[0][q] = 1

r = 1

for i in range(1, n):
    r = r * 10 % 13
    # for l in range(10):
    #     r[l] = r[l] * 10 % 13

    #print(r)

    if s[n-i-1] == "?":
        for j in range(10):
            q = j * r % 13
            for k in range(13):
                dp[i][k] += dp[i-1][k-q] % MOD
    
    else:
        q = int(s[n-i-1]) * r % 13
        #print(q)
        for k in range(13):
            dp[i][k] += dp[i-1][k-q] % MOD
    #print(dp[i])

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

Submission status: Accepted

Solution code:
S = input()
INF = 10 ** 9 + 7
length = len(S)
tmp = 1
mod = 0
cnt = 0
arr = []
for i in reversed(range(length)):
    if S[i] == "?":
        arr.append(tmp)
        cnt += 1
    else:
        mod += (tmp * int(S[i])) % 13
        mod %= 13
    tmp = (tmp * 10) % 13
tar = (5 - mod) % 13

dp = [[0 for _ in range(13)] for _ in range(cnt + 3)]
dp[0][0] = 1
for i in range(1, cnt + 1):
    for j in range(13):
        for k in range(10):
            dp[i][(j + arr[i - 1] * k) % 13] += dp[i - 1][j]
            dp[i][(j + arr[i - 1] * k) % 13] %= INF
ans = dp[cnt][tar]
print(ans)

Submission status: Accepted

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

print(dp[L][5])

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# 実装を行う関数
def resolve(test_def_name=""):
    s = list(input())

    s.reverse()

    devval = pow(10, 9) + 7

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

    # 初期値設定
    if s[0] == "?":
        for j in range(10):
            dp[0][j] += 1
    else:
        dp[0][int(s[0]) % 13] += 1

    # DP
    for i in range(1, len(s)):
        for j in range(10):
            if s[i] != "?" and s[i] != str(j):
                continue

            # ここを改善しないと無理。pow(10,100万)とか不可能・・。TLE・・。
            aaa = j * pow(10, i, 13)

            # 前DPの値を今DPに加算
            for k in range(13):
                dp[i][(aaa + k) % 13] = (dp[i][(aaa + k) % 13] + dp[i - 1][k] % devval) % devval

    # 余り5の要素数が答え
    print(dp[len(s) - 1][5])


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """??2??5"""
        output = """768"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """?44"""
        output = """1"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """7?4"""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_4(self):
        test_input = """?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76???"""
        output = """153716888"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def test_1original_1(self):
        test_input = """?"""
        output = """1"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import product
s = list(input())
MOD = 10**9+7
c = Counter([0])
ds = list(range(10))
mods = list(range(13))

ten_power = 1
while s:
    char = s.pop()
    if char == '?':
        cand = ds
    else:
        cand = [int(char)]
    nc = Counter()
    for key, d in product(mods, cand):
        new_key = (key + d * ten_power) % 13
        nc[new_key] += c[key]
        nc[new_key] %= MOD
    c = nc
    ten_power *= 10
    ten_power %= 13

print(nc[5])

Submission status: Accepted

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

numbers = list(range(10))
for i in range(n):
    next_nums = numbers if s[i] == '?' else [int(s[i])]
    for j in range(13):
        for k in next_nums:
            jj = (10 * j + k) % 13
            dp[i + 1][jj] = (dp[i + 1][jj] + dp[i][j]) % mod
print(dp[n][5])

Submission status: Accepted

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

Submission status: Accepted

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


def main():
  S = input()[:-1]
  dp = [[0]*13 for _ in range(len(S)+1)]
  dp[0][0] = 1

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

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


if(__name__ == '__main__'):
  main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
from collections import defaultdict
def input(): return sys.stdin.readline().rstrip()


def convolve(x, y):
    MOD = 10**9+7
    z = np.convolve(x, y) % MOD
    z[:12] += z[13:25]
    return z[:13] % MOD


def main():
    mod = 10**9+7
    S = input()[::-1]
    dp = np.zeros((len(S), 13), dtype='int64')
    amari = 1
    if S[0] == '?':
        for j in range(10):
            dp[0][j] = 1
    else:
        dp[0][int(S[0])] = 1

    for i in range(1, len(S)):
        arr = np.zeros(13, dtype='int64')
        amari = 10*amari % 13
        if S[i] == '?':
            for si in range(10):
                arr[amari*si % 13] += 1
        else:
            arr[amari*int(S[i]) % 13] = 1
        dp[i] = convolve(dp[i-1], arr)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()


def main():
    mod = 10**9+7
    S = input()[::-1]
    amari = 1
    dp = [[0]*13 for i in range(len(S))]
    if S[0] == '?':
        for j in range(10):
            dp[0][j] = 1
    else:
        dp[0][int(S[0])] = 1

    for i in range(1, len(S)):
        amari = 10*amari % 13
        if S[i] == '?':
            for j in range(13):
                for si in range(10):
                    dp[i][(j+amari*si) % 13] += dp[i-1][j]
                    dp[i][(j+amari*si) % 13] %= mod

        else:
            for j in range(13):
                dp[i][(j+amari*int(S[i])) % 13] = dp[i-1][j]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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

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

print(dp[-1][5])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    s=input()
    N=len(s)
    dp=[[0]*13 for i in range(N+1)]
    dp[0][0]=1
    cur=1
    for i in range(1,N+1):
        si=s[-i]
        if si.isnumeric():
            si=int(si)
            for j in range(13):
                nj=(j+cur*si)%13
                dp[i][nj]+=dp[i-1][j]
                
        else:
            tsum=0
            for j in range(13):
                for k in range(10):
                    nj=(j+k*cur)%13
                    dp[i][nj]+=dp[i-1][j]
                    dp[i][nj]%=mod

        cur*=10
        cur%=13
    print(dp[-1][5])






if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
s = list(input())
dp = [[0]*13 for _ in range(100005)]
n = len(s)
res = 0
mod = 10**9+7
dp[0][0] = 1
for i in range(n):
    c = int(s[i]) if s[i] !='?' else -1
    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[n][5])

Submission status: Accepted

Solution code:
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    s = list(input())
    l = len(s)
    dp = [[0 for _ in range(13)] for __ in range(l + 1)]
    dp[0][0] = 1

    for i, si in enumerate(s):
        base = pow(10, l - i - 1, 13)

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

    print(dp[l][5])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from copy import copy

MOD = 10**9 + 7
s = input()
count = [0 for _ in range(13)]
count[0] = 1
for i in range(len(s)):
    new = [0 for _ in range(13)]
    for m in range(13):
        new[(m * 10) % 13] = count[m]
    count = new
    if s[i] != "?":
        div = int(s[i])
        count = count[-div:] +  count[:-div]
    else:
        new = [0 for _ in range(13)]
        pre = sum(count[:3])
        SUM = sum(count) % MOD
        for j in range(13):
            pre += count[(j+3) % 13]
            pre -= count[j % 13]
            new[j] = (SUM - pre) % MOD
        count = new
print(count[5])

Submission status: Accepted

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

S=list(input().rstrip('\n'))

kake10 = [0,10,7,4,1,11,8,5,2,12,9,6,3]
now = {0:1,1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0,10:0,11:0,12:0}
for i in S:
  now = {kake10[x]:now[x] for x in range(13)}
  if i=='?':
    now2 = {x:sum(now[(x+y)%13] for y in range(4,14))%1000000007 for x in range(13)}
    now = now2
  else:
    a = int(i)
    now = {(x+a)%13:now[x] for x in range(13)}
print(now[5])

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

S = input()
N = len(S)

dp = [[0] * 13 for i in range(N)]
str_int = '0123456789'
if S[0] in str_int:
    dp[0][int(S[0])] += 1
else:
    for i in range(10):
        dp[0][i] += 1

for i in range(1, N):
    if S[i] in str_int:
        # 前の段
        for j in range(13):
            dp[i][(10 * j + int(S[i])) % 13] += (dp[i - 1][j] % mod)
    else:
        # 前の段
        for j in range(13):
            # 後ろの段
            # ?なら0 ~ 10で回す
            for l in range(10):
                dp[i][(10 * j + l) % 13] += (dp[i - 1][j] % mod)

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

Submission status: Accepted

Solution code:
m=10**9+7
s=input()
d=[1]+[0]*12
for i in range(len(s)):
 if s[i]== "?":d=[sum(d[(j-k)*4%13]for k in range(10))%m for j in range(13)]
 else:d=[d[(j-int(s[i]))*4%13]%m for j in range(13)]
print(d[5])

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from functools import reduce, lru_cache
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    s = S()

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

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
import bisect
import heapq
from collections import Counter


def input():
    return sys.stdin.readline().rstrip()


def main():
    mod = 10 ** 9 + 7
    S = list(input())
    l = len(S)
    dp = [[0] * 13 for _ in range(l + 1)]

    dp[0][0] = 1
    for j in range(1, l + 1):
        jp = j - 1
        if S[jp] == "?":
            for k in range(13):
                kk = k * 10
                for q in range(10):
                    new_k = (kk + q) % 13
                    dp[j][new_k] += dp[jp][k]
            for k in range(13):
                dp[j][k] %= mod
        else:
            n = int(S[jp])
            for k in range(13):
                new_k = (k * 10 + n) % 13
                dp[j][new_k] += dp[jp][k]
                dp[j][new_k] %= mod
    print(dp[l][5])


if __name__ == "__main__":
    main()