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
def SI(): return sys.stdin.readline().strip()
MOD = 10 ** 9 + 7


def main(): 
    S = SI()

    # 桁DP。この init で dp_table[len(S)][13] となる。前後逆になるので注意。
    dp_table = [[0 for _ in range(13)] for _ in range(len(S))]

    # 最初の桁を見る。
    if S[0] == '?':
        region = range(10)
    else:
        region = [int(S[0]),]

    for i in region:
        dp_table[0][i] = 1

    # 以降の桁を見ていく。
    for digit in range(1, len(S)):
        if S[digit] == '?':
            region = range(10)
        else:
            region = [int(S[digit]),]

        for prev_res, comb in enumerate(dp_table[digit-1]):
            for x in region:
                res = (prev_res*10+x)%13
                dp_table[digit][res] = (dp_table[digit][res] + comb)%MOD

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

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
MOD = 10**9 + 7
def main():
    S = input()
    N = len(S)-1
 
    dp = [0] * 13
    if S[0] == '?':
        for i in range(10):
            dp[i] = 1
    else:
        dp[int(S[0])] = 1
 
    for i in range(1,N):
        dppre = dp
        dp = [0] * 13
 
        if S[i] == '?':
            R = range(10)
        else:
            R = [int(S[i])]
        
        for j in range(13):
            for k in R:
                dp[(j * 10 + k) % 13 ] += dppre[j]
        for j in range(13):
            dp[j] %= MOD
 
    print(dp[5])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
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 II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7


from functools import lru_cache


def main(): 
    S = SI()

    # 桁DP
    dp_table = [[0 for _ in range(13)] for _ in range(len(S))]

    # 最初の桁を見る。
    if S[0] == '?':
        region = range(10)
    else:
        region = [int(S[0]),]
    for i in region:
        dp_table[0][i] = 1

    # 以降の桁を見ていく。
    for digit in range(1, len(S)):
        if S[digit] == '?':
            region = range(10)
        else:
            region = [int(S[digit]),]

        for prev_res, comb in enumerate(dp_table[digit-1]):
            for x in region:
                res = (prev_res*10+x)%13
                dp_table[digit][res] = (dp_table[digit][res] + comb)%MOD

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



main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
MOD = 10**9 + 7
def main():
    S = input()
    N = len(S)-1
 
    if S[0] == '?':
        dp = [1,1,1,1,1,1,1,1,1,1,0,0,0]
    else:
        dp = [0] * 13
        dp[int(S[0])] = 1
 
    for i in range(1,N):
        dppre = dp
        dp = [0] * 13
 
        if S[i] == '?':
            R = range(10)
        else:
            R = [int(S[i])]
        
        for j in range(13):
            for k in R:
                dp[(j * 10 + k) % 13 ] += dppre[j]
        for j in range(13):
            dp[j] %= MOD
 
    print(dp[5])
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

    if S[0] == '?':
        dp = [1,1,1,1,1,1,1,1,1,1,0,0,0]
    else:
        dp = [0,0,0,0,0,0,0,0,0,0,0,0,0]
        dp[int(S[0])] = 1

    for i in range(1,N):
        dppre = dp
        dp = [0] * 13

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

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

    print(dp[5])
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

    if S[0] == '?':
        dp = [1,1,1,1,1,1,1,1,1,1,0,0,0]
    else:
        dp = [0,0,0,0,0,0,0,0,0,0,0,0,0]
        dp[int(S[0])] = 1

    for i in range(1,N):
        dppre = dp
        dp = [0] * 13

        if S[i] == '?':
            R = range(10)
        else:
            R = [int(S[i])]
        
        for j in range(13):
            for k in R:
                dp[(j * 10 + k) % 13 ] += dppre[j]
        for j in range(13):
            dp[j] %= MOD

    print(dp[5])
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

    if S[0] == '?':
        dp = [1,1,1,1,1,1,1,1,1,1,0,0,0]
    else:
        dp = [0,0,0,0,0,0,0,0,0,0,0,0,0]
        dp[int(S[0])] = 1

    for i in range(1,N):
        dppre = dp
        dp = [0,0,0,0,0,0,0,0,0,0,0,0,0]

        if S[i] == '?':
            R = range(10)
        else:
            R = [int(S[i])]
        
        for j in range(13):
            for k in R:
                dp[(j * 10 + k) % 13 ] += dppre[j]
        for j in range(13):
            dp[j] %= MOD

    print(dp[5])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S = input()
S = list(S)
MOD = 1000000007
l = [[0 for j in range(10)] for i in range(6)]
for i in range(6):
    for j in range(10):
        l[i][j] = j * 10**i % 13

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

for i in range(len(S)-1, -1, -1):
    ir = len(S)-1 - i
    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[ir+1][(k + l[ir%6][j]) % 13] += dp[ir][k]
    for k in range(13):
        dp[ir+1][k] %= MOD

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

Submission status: Accepted

Solution code:

M = 10 ** 9 + 7
s = raw_input().strip()

num = 0
q_list = []
d = 1
for i in range(len(s) - 1, -1, -1):
	c = s[i]
	if c != "?":
		num = (num + int(c) * d) % 13
	else:
		q_list.append(d)
	d = (d * 10) % 13

counts = [0] * 13
counts[0] = 1
counts_save = [0] * 13
for d in q_list:
	for i in range(13):
		counts_save[i] = counts[i] % M
	for n in range(1, 10):
		r = (d * n) % 13
		for m in range(13):
			counts[(r + m) % 13] += counts_save[m]

print(counts[(13 + 5 - num) % 13] % M)

Submission status: Accepted

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

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

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

    for i in range(N):
        dppre = dp
        dp = [0] * 13

        if S[i] == '?':
            R = range(10)
        else:
            R = [int(S[i])]
        
        for j in range(13):
            for k in R:
                dp[(j * 10 + k) % 13 ] += dppre[j]
        for j in range(13):
            dp[j] %= MOD

    print(dp[5])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
""" dpはi桁,あまりj
[[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
"""
MOD = 10**9+7

S = str(input())
S = S[::-1]
n = len(S)

dp = [[0]*(13) for _ in range(n+1)]
dp[0][0]=1 #0を割ったあまりは0

q = 1 # はじめの1桁のときはあまりは1

# i桁目のあまりが何通りあるか
for i in range(1,n+1): # 「1-n」桁まで
  s = S[i-1]
  for j in range(13): # 13で割ったあまり
    
    if s == '?': # ?の場合は0-9を計算する
      for k in range(10):
        dp[i][(j+k*q)%13] += dp[i-1][j] # i-1桁目からi桁目 +=を忘れずに！
    else:
      k = int(s)
      dp[i][(j+k*q)%13] += dp[i-1][j] # i-1桁目からi桁目
  for m in range(13):
    dp[i][m] %= MOD
  q = (10*q)%13 # 「10^iをqで割ったあまり」

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2**31-1)
input = sys.stdin.readline
write = sys.stdout.write
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = True



MOD = 10**9 + 7
def main():
    S = input()
    N = len(S)-1
    dp = [0] * 13
    

    if S[0] == '?':
        R = range(10)
    else:
        R = [int(S[0])]

    for i in R:
        dp[i] = 1

    for i in range(1,N):
        if S[i] == '?':
            R = range(10)
        else:
            R = [int(S[i])]


        dppre = dp
        dp = [0] * 13
        for j in range(13):
            for k in R:
                dp[(j * 10 + k) % 13 ] += dppre[j]
        for j in range(13):
            dp[j] %= MOD
    
    print(dp[5])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

# やりやすさのため、小さい桁からいけるように逆順にしておく
S=input()[::-1]
N=len(S)

# dp[i][j] := 下からi桁を考えた時，13で割ったあまりがjであるものの数
dp=list2d(N+1, 13, 0)
dp[0][0]=1
mul=1
for i in range(N):
    for j in range(13):
        # ?だったら0~9を全て遷移させる
        if S[i]=='?':
            for k in range(10):
                # 桁を合わせる
                nxt=k*mul
                dp[i+1][(j+nxt)%13]+=dp[i][j]
                dp[i+1][(j+nxt)%13]%=MOD      
        else:
            # 決まっていたらその数字のみ遷移させる
            nxt=int(S[i])*mul
            dp[i+1][(j+nxt)%13]+=dp[i][j]
            dp[i+1][(j+nxt)%13]%=MOD
    # 桁を合わせ用(10万桁とか直接使ったら死ぬので、毎回ここでMOD13する)
    mul*=10
    mul%=13
# 最終的にN桁終わって余り5の数が答え
print(dp[N][5])

Submission status: Accepted

Solution code:
d=[1]+[0]*12
for c in input():d=[sum(d[(int(i)-k)*9%13]for i in((c,range(10))[c>'9']))%(10**9+7)for k in range(13)]
print(d[5])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

s = s()[::-1]
n = len(s)
# dp[i][j] := 先頭 i + 1 文字として考えられるもののうち，13 で割ったあまりが j であるものの数
dp = [[0 for _ in range(13)] for _ in range(n)]
# 初期値
if s[0] == "?":
    for j in range(10):
        dp[0][j] = 1
else:
    dp[0][int(s[0])] = 1

# dp[i + 1][(j + x * d) % 13] += dp[i][j]，前のやつの余りj（j=0～12に集約されている）を用いて，次のやつを考えていく，
# xを10倍していくが，値が大きくなりすぎるとまずいので，mod13を毎回とる（結果は変わらない）
x = 10
for i in range(n - 1):
    if s[i + 1] == "?":
        start = 0
        end = 10
    else:
        start = int(s[i + 1])
        end = int(s[i + 1]) + 1
    for d in range(start, end):
        for j in range(13):
            dp[i + 1][(j + x * d) % 13] += dp[i][j]
            dp[i + 1][(j + x * d) % 13] %= mod
    x = x * 10 % 13

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

Submission status: Accepted

Solution code:
d=[1]+[0]*12
for c in input():
	e=[0]*13
	for k in([c],range(10))[c>'9']:
		for j in range(13):t=(j*10+int(k))%13;e[t]+=d[j];e[t]%=10**9+7
	d=e
print(d[5])

Submission status: Accepted

Solution code:
r=range;d=[1]+[0]*12
for s in input():
 p=[0]*13
 for j in r(13):
  for k in ([s],r(10))[s>'9']:t=(j*10+int(k))%13;p[t]+=d[j];p[t]%=10**9+7
 d=p
print(d[5])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2**31-1)
input = sys.stdin.readline
write = sys.stdout.write
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = True



MOD = 10**9 + 7
class ModInt:

    def __init__(self, x):
        self.x = x.x if isinstance(x, ModInt) else x % MOD

    __str__ = lambda self:str(self.x)
    __repr__ = __str__
    __int__ = lambda self: self.x
    __index__ = __int__

    __add__ = lambda self, other: ModInt(self.x + ModInt(other).x)
    __sub__ = lambda self, other: ModInt(self.x - ModInt(other).x)
    __mul__ = lambda self, other: ModInt(self.x * ModInt(other).x)
    __pow__ = lambda self, other: ModInt(pow(self.x, ModInt(other).x, MOD))
    __mod__ = lambda self, other: ModInt(self.x % ModInt(other).x)
    __truediv__ = lambda self, other: ModInt(self.x * pow(ModInt(other).x, MOD - 2, MOD))
    __floordiv__ = lambda self, other: ModInt(self.x // ModInt(other).x)
    __radd__ = lambda self, other: ModInt(other + self.x)
    __rsub__ = lambda self, other: ModInt(other - self.x)
    __rpow__ = lambda self, other: ModInt(pow(other, self.x, MOD))
    __rmod__ = lambda self, other: ModInt(other % self.x)
    __rmul__ = lambda self, other: ModInt(other * self.x)
    __rtruediv__ = lambda self, other: ModInt(other * pow(self.x, MOD - 2, MOD))
    __rfloordiv__ = lambda self, other: ModInt(other // self.x)

    __lt__ = lambda self, other: self.x < ModInt(other).x
    __gt__ = lambda self, other: self.x > ModInt(other).x
    __le__ = lambda self, other: self.x <= ModInt(other).x
    __ge__ = lambda self, other: self.x >= ModInt(other).x
    __eq__ = lambda self, other: self.x == ModInt(other).x
    __ne__ = lambda self, other: self.x != ModInt(other).x


def main():
    S = input()
    N = len(S)-1
    dp = [[0] * 13  for _   in range(N)]
    dp[0] = [0 for _ in range(13)]
    
    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] == '?':
            R = range(10)
        else:
            R = [int(S[i])]

        for j in range(13):
            for k in R:
                dp[i][(j * 10 + k) % 13 ] = (dp[i][(j * 10 + k) % 13 ] + dp[i-1][j]) 
        for j in range(13):
            dp[i][j] %= MOD
    
    print(dp[len(S)-2][5])









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

Submission status: Accepted

Solution code:
d=[1]+[0]*12
for c in input():
 p=[0]*13
 for j in range(13):
  for k in range(10):t=(j*10+k)%13;p[t]+=d[j]*(c>'9'or k==int(c));p[t]%=10**9+7
 d=p
print(d[5])

Submission status: Accepted

Solution code:
r=range
d=[0]*13
d[0]=1
for s in input():
	e=[0]*13
	for j in r(13):
		for k in([s],r(10))[s>'9']:e[(j*10+int(k))%13]+=d[j]
	d=[e%(10**9+7)for e in e]
print(d[5])

Submission status: Accepted

Solution code:
d=[1]+[0]*12
for c in input():
	e=[0]*13
	for k in(range(10)if c>'>'else[int(c)]):
		for j in range(13):t=(j*10+k)%13;e[t]+=d[j];e[t]%=10**9+7
	d=e
print(d[5])

Submission status: Accepted

Solution code:
s = input()
dp = [0 for _ in range(13)]
dp[0] = 1
c = 1000000007
m = 1
r13 = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
r10 = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
for i in range(len(s) - 1, -1, -1):
    ndp = [0 for _ in r13]
    if s[i] == "?":
        for j in r10:
            jm = j * m
            for k in r13:
                index = (jm + k) % 13
                ndp[index] = (ndp[index] + dp[k]) % c
    else:
        jm = int(s[i]) * m
        for k in r13:
            index = (jm + k) % 13
            ndp[index] = (ndp[index] + dp[k]) % c
    dp = ndp[:]
    m = m * 10 % 13
print(dp[5])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2**31-1)
input = sys.stdin.readline
write = sys.stdout.write
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = True



MOD = 10**9 + 7
class ModInt:

    def __init__(self, x):
        self.x = x.x if isinstance(x, ModInt) else x % MOD

    __str__ = lambda self:str(self.x)
    __repr__ = __str__
    __int__ = lambda self: self.x
    __index__ = __int__

    __add__ = lambda self, other: ModInt(self.x + ModInt(other).x)
    __sub__ = lambda self, other: ModInt(self.x - ModInt(other).x)
    __mul__ = lambda self, other: ModInt(self.x * ModInt(other).x)
    __pow__ = lambda self, other: ModInt(pow(self.x, ModInt(other).x, MOD))
    __mod__ = lambda self, other: ModInt(self.x % ModInt(other).x)
    __truediv__ = lambda self, other: ModInt(self.x * pow(ModInt(other).x, MOD - 2, MOD))
    __floordiv__ = lambda self, other: ModInt(self.x // ModInt(other).x)
    __radd__ = lambda self, other: ModInt(other + self.x)
    __rsub__ = lambda self, other: ModInt(other - self.x)
    __rpow__ = lambda self, other: ModInt(pow(other, self.x, MOD))
    __rmod__ = lambda self, other: ModInt(other % self.x)
    __rmul__ = lambda self, other: ModInt(other * self.x)
    __rtruediv__ = lambda self, other: ModInt(other * pow(self.x, MOD - 2, MOD))
    __rfloordiv__ = lambda self, other: ModInt(other // self.x)

    __lt__ = lambda self, other: self.x < ModInt(other).x
    __gt__ = lambda self, other: self.x > ModInt(other).x
    __le__ = lambda self, other: self.x <= ModInt(other).x
    __ge__ = lambda self, other: self.x >= ModInt(other).x
    __eq__ = lambda self, other: self.x == ModInt(other).x
    __ne__ = lambda self, other: self.x != ModInt(other).x


def main():
    S = input()
    N = len(S)-1
    dp = [[0] * 13  for _   in range(N)]
    dp[0] = [0 for _ in range(13)]
    
    if S[0] == '?':
        for i in range(10):
            dp[0][i] = 1
    else:
        dp[0][int(S[0])] = 1

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

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









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

Submission status: Accepted

Solution code:
d=[1]+[0]*12
for i,c in enumerate(input()):
 p=[0]*13
 for j in range(13):
  for k in range(10):p[(j*10+k)%13]+=d[j]*(c>'9'or k==int(c))
 d=[t%(10**9+7)for t in p]
print(d[5])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2**31-1)
input = sys.stdin.readline
write = sys.stdout.write
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = True



MOD = 10**9 + 7
class ModInt:

    def __init__(self, x):
        self.x = x.x if isinstance(x, ModInt) else x % MOD

    __str__ = lambda self:str(self.x)
    __repr__ = __str__
    __int__ = lambda self: self.x
    __index__ = __int__

    __add__ = lambda self, other: ModInt(self.x + ModInt(other).x)
    __sub__ = lambda self, other: ModInt(self.x - ModInt(other).x)
    __mul__ = lambda self, other: ModInt(self.x * ModInt(other).x)
    __pow__ = lambda self, other: ModInt(pow(self.x, ModInt(other).x, MOD))
    __mod__ = lambda self, other: ModInt(self.x % ModInt(other).x)
    __truediv__ = lambda self, other: ModInt(self.x * pow(ModInt(other).x, MOD - 2, MOD))
    __floordiv__ = lambda self, other: ModInt(self.x // ModInt(other).x)
    __radd__ = lambda self, other: ModInt(other + self.x)
    __rsub__ = lambda self, other: ModInt(other - self.x)
    __rpow__ = lambda self, other: ModInt(pow(other, self.x, MOD))
    __rmod__ = lambda self, other: ModInt(other % self.x)
    __rmul__ = lambda self, other: ModInt(other * self.x)
    __rtruediv__ = lambda self, other: ModInt(other * pow(self.x, MOD - 2, MOD))
    __rfloordiv__ = lambda self, other: ModInt(other // self.x)

    __lt__ = lambda self, other: self.x < ModInt(other).x
    __gt__ = lambda self, other: self.x > ModInt(other).x
    __le__ = lambda self, other: self.x <= ModInt(other).x
    __ge__ = lambda self, other: self.x >= ModInt(other).x
    __eq__ = lambda self, other: self.x == ModInt(other).x
    __ne__ = lambda self, other: self.x != ModInt(other).x


def main():
    S = input()
    N = len(S)-1
    dp = [[0] * 13  for _   in range(N)]
    dp[0] = [ModInt(0) for _ in range(13)]
    
    if S[0] == '?':
        for i in range(10):
            dp[0][i] = ModInt(1)
    else:
        dp[0][int(S[0])] = ModInt(1)

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

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









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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2**31-1)
input = sys.stdin.readline
write = sys.stdout.write
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = True



MOD = 10**9 + 7
class ModInt:

    def __init__(self, x):
        self.x = x.x if isinstance(x, ModInt) else x % MOD

    __str__ = lambda self:str(self.x)
    __repr__ = __str__
    __int__ = lambda self: self.x
    __index__ = __int__

    __add__ = lambda self, other: ModInt(self.x + ModInt(other).x)
    __sub__ = lambda self, other: ModInt(self.x - ModInt(other).x)
    __mul__ = lambda self, other: ModInt(self.x * ModInt(other).x)
    __pow__ = lambda self, other: ModInt(pow(self.x, ModInt(other).x, MOD))
    __mod__ = lambda self, other: ModInt(self.x % ModInt(other).x)
    __truediv__ = lambda self, other: ModInt(self.x * pow(ModInt(other).x, MOD - 2, MOD))
    __floordiv__ = lambda self, other: ModInt(self.x // ModInt(other).x)
    __radd__ = lambda self, other: ModInt(other + self.x)
    __rsub__ = lambda self, other: ModInt(other - self.x)
    __rpow__ = lambda self, other: ModInt(pow(other, self.x, MOD))
    __rmod__ = lambda self, other: ModInt(other % self.x)
    __rmul__ = lambda self, other: ModInt(other * self.x)
    __rtruediv__ = lambda self, other: ModInt(other * pow(self.x, MOD - 2, MOD))
    __rfloordiv__ = lambda self, other: ModInt(other // self.x)

    __lt__ = lambda self, other: self.x < ModInt(other).x
    __gt__ = lambda self, other: self.x > ModInt(other).x
    __le__ = lambda self, other: self.x <= ModInt(other).x
    __ge__ = lambda self, other: self.x >= ModInt(other).x
    __eq__ = lambda self, other: self.x == ModInt(other).x
    __ne__ = lambda self, other: self.x != ModInt(other).x


def main():
    S = list(input())
    N = len(S)-1
    dp = [[0] * 13  for _   in range(N)]
    dp[0] = [ModInt(0) for _ in range(13)]
    
    if S[0] == '?':
        for i in range(10):
            dp[0][i] = ModInt(1)
    else:
        dp[0][int(S[0])] = ModInt(1)

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

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









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

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

s = s()[::-1]
n = len(s)
# dp[i][j] := 先頭 i + 1 文字として考えられるもののうち，13 で割ったあまりが j であるものの数
dp = [[0 for _ in range(13)] for _ in range(n)]
# 初期値
if s[0] == "?":
    for j in range(10):
        dp[0][j] = 1
else:
    dp[0][int(s[0])] = 1

# dp[i + 1][(10 * j + d) % 13] += dp[i][j]，i桁目がd（違う）
x = 10
for i in range(n - 1):
    if s[i + 1] == "?":
        start = 0
        end = 10
    else:
        start = int(s[i + 1])
        end = int(s[i + 1]) + 1
    for d in range(start, end):
        for j in range(13):
            dp[i + 1][(j + x * d) % 13] += dp[i][j]
            dp[i + 1][(j + x * d) % 13] %= mod
    x = x * 10 % 13

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
d=[0]*13
d[0]=1
for c in input():
	e=[0]*13
	for k in(range(10)if c>'>'else[int(c)]):
		for j in range(13):t=(j*10+k)%13;e[t]+=d[j];e[t]%=10**9+7
	d=e
print(d[5])

Submission status: Accepted

Solution code:
def d_digits_parade(S, MOD=10**9 + 7):
    modulo = 13  # 13で割ったあまりを考えている
    # editorialでは2次元配列を考えているが、こうするとメモリを節約できる
    dp = [0] * modulo  # dp[k]: 13で割ったあまりがkの場合の数
    dp[0] = 1  # 初期値を0とすると、これを13で割ったあまりは0

    # Sを下の桁から見ていく
    # ex. 1?2?3: 0 - 3 - ?3 - 2?3 - ...
    mul = 1
    for c in S[::-1]:
        dp_next = [0] * modulo
        if c == '?':
            for k in range(10):  # ?に対し1桁の数字のすべてを試す
                for j in range(modulo):
                    # k * mul: mulの位がk、j: それより下の桁についてのあまり
                    # なので、このような遷移
                    dp_next[(k * mul + j) % modulo] += dp[j]
                    dp_next[(k * mul + j) % modulo] %= MOD
        else:
            k = int(c)
            for j in range(modulo):
                dp_next[(k * mul + j) % modulo] += dp[j]
                dp_next[(k * mul + j) % modulo] %= MOD
        # a*10**d % modulo = (a*(10**d % modulo)) % modulo なので、先に剰余を取る
        # (多倍長整数を持ち出さなくてよくなる)
        mul = (mul * 10) % modulo
        dp = dp_next
    return dp[5]

S = input()
print(d_digits_parade(S))

Submission status: Accepted

Solution code:
D = 10**9+7
S = input()
mod_table = [[0]*13]
mod_table[0][0] = 1

for i, s in enumerate(S):
    mod_table.append([0]*13)
    if s == "?":
        for num in range(10):
            for d in range(13):
                mod_table[i+1][(d*10+num)%13] += mod_table[i][d]
    else:
        num = int(s)
        for d in range(13):
            mod_table[i+1][(d*10+num)%13] += mod_table[i][d]
    mod_table[i+1] = [m%D for m in mod_table[i+1]]

print(mod_table[-1][5] % D)

Submission status: Accepted

Solution code:
d=[0]*13
d[0]=1
for c in input():
	e=[0]*13
	for k in(range(10)if c>'>'else[int(c)]):
		for j in range(13):e[(j*10+k)%13]+=d[j]
	d=[e%(10**9+7)for e in e]
print(d[5])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

s = ns()

dp = [0] * 13
dp[0] = 1
mod = 1000000007
for v in s:
    ndp = [0] * 13
    if v == "?":
        for j in range(13):
            for k in range(10):
                nj = (j*10+k)%13
                ndp[nj] += dp[j]
                ndp[nj] %= mod
    else:
        k = ord(v)-ord("0")
        for j in range(13):
            nj = (j*10+k)%13
            ndp[nj] += dp[j]
            ndp[nj] %= mod
    dp = ndp
print(dp[5])

Submission status: Accepted

Solution code:
t=13
S=input()
d=[0]*t
d[0]=1
for i in range(len(S)):
  n=[0]*t
  for j in range(t):
    for k in range(10):
      if S[i]=='?' or int(S[i])==k:n[(10*j+k)%t]+=d[j]
  for j in range(t):d[j]=n[j]%(10**9+7)
print(d[5])

Submission status: Accepted

Solution code:
t=13
S=input()
d=[0]*t
d[0]=1
for i in range(len(S)):
  n=[0]*t
  for j in range(t):
    for k in range(10):
      if S[i]=='?' or int(S[i])==k:n[(10*j+k)%t]+=d[j]
  for j in range(t): d[j]=n[j]%(10**9+7)
print(d[5])

Submission status: Accepted

Solution code:
MOD = 1000000007
m = 13
S = input()
start = int(S.replace('?', '0')) % m
dp = [0] * 13; dp[start] = 1
for i, s in enumerate(S[::-1]):
    nextDP = [0] * 13
    if (s != '?'): continue
    mul = pow(10, i, m)
    for j in range(10):
        for k in range(m):
            nextDP[(mul*j + k) % m] += dp[k]
            nextDP[(mul*j + k) % m] %= MOD
    dp = nextDP
print(dp[5])

Submission status: Accepted

Solution code:
t=13
S=input()
d=[0]*t
d[0]=1
for i in range(len(S)):
  n=[0]*t
  for j in range(t):
    for k in range(10):
      if S[i]=='?' or int(S[i])==k: n[(10*j+k)%t]+=d[j]
  for j in range(t): d[j]=n[j]%(10**9+7)
print(d[5])