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

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

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

Submission status: Accepted

Solution code:
def main():
    M=10**9+7
    r=tuple(tuple((j-k)*9%13for j in range(10))for k in range(13))
    d=[1]+[0]*12
    for c in input():
        if c > '9':
            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[5])
main()

Submission status: Accepted

Solution code:
MOD = int(1e9+7)


def main():
    S = input()
    x = [1] * 6
    for i in range(1, 6):
        x[i] = (x[i-1] * 10) % 13
    dp = [[0] * 13 for _ in range(len(S)+1)]
    dp[0][0] = 1
    for i, c in enumerate(S[::-1]):
        m = x[i % 6]
        if c == "?":
            for j in range(13):
                for k in range(10):
                    dp[i+1][(j+m*k) % 13] += dp[i][j]
            for j in range(13):
                dp[i+1][j] %= MOD
        else:
            for j in range(13):
                dp[i+1][(j+m*int(c)) % 13] = dp[i][j]
    print(dp[len(S)][5])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

if s[0] == '?':
    dp[0][0:9] = [1 for x in range(10)]
else:
    dp[0][int(s[0])] = 1

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

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

Submission status: Accepted

Solution code:
import math
S=input()
dp=[0]*13
dp[0]=1
# dp[k] 13で割った余りkのパターン数
mod = 1000000007

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

print(dp[5])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
M = 10**9+7
r = tuple(tuple((j-i) * 4 % 13 for i in range(10)) for j in range(13))
d = [1] + [0] * 12
for c in input():
    if c > "9":
        d = [(sum(d[i] for i in j)) % M for j in r]
    else:
        d = [d[((j - int(c)) * 4 % 13)] for j in range(13)]
print(d[5])

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
S = list(input())
u = 10**9+7
d = len(S)
dp = [0]*13
dp[0] = 1
m = 1

for i in range(d-1,-1,-1):
    tmp = [0]*13
    a = S[i]
    if a=='?':
        for j in range(10):
            c = j*m
            for k in range(13):
                n = (c+k)%13
                tmp[n] += dp[k]
                tmp[n] %= u
    else:
        c = int(a)*m
        for k in range(13):
            n = (c+k)%13
            tmp[n] += dp[k]
            tmp[n] %= u
    m *= 10
    m %= 13
    dp = tmp
print(dp[5])

Submission status: Accepted

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math

S = input()
amari = [1, 10, 9, 12, 3, 4]
kurai = 0
hatena = []
base = 0
for i in range(len(S)):
	#print(S[len(S) - 1 - i])
	if S[len(S) - 1 - i] == '?':
		hatena.append(kurai)
	else:
		base += (int(S[len(S) - 1 - i])*amari[i % 6])
		base = base % 13
	kurai += 1

#print(base, hatena)
count13 = [0]*13
count13[base]+=1
for kurai in hatena:
	countnow = [0]*13
	for num in range(10):
		x = num * amari[kurai % 6]
		for i in range(13):
			y = (i + x) % 13
			countnow[y] += count13[i]
	for i in range(13):
		countnow[i] = countnow[i] % 1000000007
	count13 = copy.deepcopy(countnow)

print(count13[5])

Submission status: Accepted

Solution code:
# standart input
# n = int(input())
# a = list(map(int, input().split()))

N = 13
MOD = 10 ** 9 + 7

s = input()[::-1]

dp = [0 for i in range(N)]
nextdp = [0 for i in range(N)]
zeros = [0 for i in range(N)]
dp[0] = 1

r = 1
for i, si in enumerate(s):
    nextdp = zeros[:]

    for j in range(10):
        jj = j
        if si == "?":
            pass
            # c = (j * 10 ** i) % N
        elif j == 0:
            jj = int(si)
        else:
            break

        for k in range(N):
            l = (k + r * jj) % N
            nextdp[l] = (nextdp[l] + dp[k]) % MOD

    dp = nextdp
    r = r * 10 % N

print(dp[5])

Submission status: Accepted

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

dp[0][0] = 1
for i in range(1, len(dp)):
    c = int(S[i-1]) if S[i-1] != '?' else -1
    for j in range(13):
        for k in range(10):
            if c != -1 and c != k:
                continue
            dp[i][(j*10+k) % 13] += dp[i-1][j]
    for j in range(13):
        dp[i][j] %= mod

print(dp[-1][5])

Submission status: Accepted

Solution code:
def main():
    mod = 10**9+7
    s = list(input())
    n = len(s)
    s = s[::-1]    

    dp = [[0]*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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
d=[0]*13
d[0]=1
m=1
mmod=1
t=input()[::-1]
mod=10**9+7
zero=[0]*13

for c in t:
    e=zero[:]
    for i in (range(10) if c=="?" else[int(c)]):
        for j in range(13):
            #e[(i*mul+j)%13]+=d[j]
            k=(i*m+j)%13
            e[k]+=d[j]
            e[k]%=1000000007
    d=e
    m=10*m%13
print(d[5])

Submission status: Accepted

Solution code:
d=[0]*13
d[0]=1
m=1
mmod=1
t=input()[::-1]
mod=10**9+7
zero=[0]*13

for c in t:
    e=zero[:]
    if c=="?":
        for i in range(10):
            for j in range(13):
                k=(i*m+j)%13
                e[k]+=d[j]
                e[k]%=mod
                
                
                
                
                
                
                
                
    else:
        for j in range(13):
            k=(int(c)*m+j)%13
            e[k]+=d[j]
            e[k]%=mod
            
            
            
            
            
            
            
            
            
    d=e
    m=10*m%13
print(d[5])

Submission status: Accepted

Solution code:
d=[0]*13
d[0]=1
m=1
mmod=1
t=input()[::-1]
mod=10**9+7
zero=[0]*13

for c in t:
    e=zero[:]
    if c=="?":
        for i in range(10):
            for j in range(13):
                k=(i*m+j)%13
                e[k]+=d[j]
                e[k]%=mod
    else:
        for j in range(13):
            k=(int(c)*m+j)%13
            e[k]+=d[j]
            e[k]%=mod
    d=e
    m=10*m%13
print(d[5])

Submission status: Accepted

Solution code:
d=[0]*13
d[0]=1
mul=1
mulmod=1
t=input()[::-1]
mod=10**9+7
zero=[0]*13

for c in t:
    e=zero[:]
    if c=="?":
        for i in range(10):
            for j in range(13):
                k=(i*mul+j)%13
                e[k]+=d[j]
                e[k]%=mod
    else:
        for j in range(13):
            k=(int(c)*mul+j)%13
            e[k]+=d[j]
            e[k]%=mod
    d=e
    mul=10*mul%13
print(d[5])

Submission status: Accepted

Solution code:
S = input()[::-1]
P = 10**9+7
c = 1
X = [1]+[0]*12
for s in S:
    Y = [0] * 13
    if s == "?":
        for i in range(10):
            for j in range(13):
                Y[(c*i+j)%13] += X[j]
                Y[(c*i+j)%13] %= P
    else:
        for j in range(13):
            Y[(c*int(s)+j)%13] = X[j]
            
    X = Y
    c = c*10%13
 
print(X[5])

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
MAX = 10**5+5
INF = 10**9
P = 1000000007

def resolve():
    s = input().strip()
    dp = [[0]*13 for _ in range(MAX)]
    dp[0][0]=1
    for i,x in enumerate(s):
        if x=='?':
            c=-1
        else:
            c=int(x)
        for j in range(10):
            if(c!=-1 and c!=j):
                continue
            for k in range(13):
                t=(k*10+j)%13
                dp[i+1][t] = dp[i+1][t]+dp[i][k]
        for j in range(13):
            dp[i+1][j]=dp[i+1][j]%P
    l=len(s)
    print(dp[l][5]%P)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
 
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意
 
s = input()
l = len(s)
MOD = 10**9+7
 
dp = [0]*13
dp[0] = 1
for i in s:
    new = [0]*13
    if i == "?":
        for i in range(10):
            for j in range(13):
                new[(10*j+i)%13] += dp[j]
    else:
        i = int(i)
        for j in range(13):
            new[(i+10*j)%13] += dp[j]
    
    for i in range(13):
        new[i] %= MOD
    dp,new = new,dp
#    print(dp)
 
print(dp[5]%MOD)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

def main():
    S = input()
    
    lenS = len(S)
    N = 13
    DP = [0] * N
    DP[0] = 1
    
    mod = 10 ** 9 + 7
    mul = 1
    for i in reversed(range(lenS)):
        nextDP = [0] *13
        c = S[i]
        if c == '?':
            for k in range(10):
                for j in range(N):
                    nextDP[(k * mul + j) %N] += DP[j]
                    nextDP[(k * mul + j) %N] %= mod

        else:
            k = int(S[i])
            for j in range(N):
                nextDP[(k * mul + j) %N] += DP[j]
                nextDP[(k * mul + j) %N] %= mod

        mul *= 10
        mul %= N
        DP = nextDP

    return DP[5]

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

Submission status: Accepted

Solution code:
M=10**9+7
r=tuple(tuple((j-i)*4%13 for i in range(10))for j in range(13))
d=[1]+[0]*12
for c in input():
  if c>"9":
    d=[(sum(d[i] for i in j))%M for j in r]
  else:
    d=[d[((j-int(c))*4%13)] for j in range(13)]
    
print(d[5])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)

import logging

# logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)

import re

# @profile
def resolve():
    S = sys.stdin.readline().split()[0]

    logger.debug(S)

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

    len_S = len(S)
    for i in range(1, len(S)):
        if S[i] == '?':
            for r in range(13):
                dp[i-1][r] %= (10**9 + 7)
                for j in range(10):
                    new_r =  j + r * 10
                    dp[i][new_r % 13] += dp[i-1][r]

        else:
            int_s = int(S[i])
            for r in range(13):
                new_r = int_s + r * 10
                dp[i][new_r % 13] += dp[i-1][r] % (10**9 + 7)

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

if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """??2??5"""
        output = """768"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """?44"""
        output = """1"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """7?4"""
        output = """0"""
        self.assertIO(input, output)
    def test_入力例_4(self):
        input = """?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76???"""
        output = """153716888"""
        self.assertIO(input, output)

Submission status: Accepted

Solution code:
import copy
S = input()
mod = 10 ** 9 + 7
N = 13
dp = [0] * N
dp[0] = 1

for i in range(len(S)):
	next_dp = [0] * N
	
	if S[i] == '?':
		for j in range(10):
			for k in range(N):
				next_dp[(10 * k + j) % N] += dp[k]
				next_dp[(10 * k + j) % N] %= mod
			
	else:
		j = int(S[i])
		
		for k in range(N):
			next_dp[(10 * k + j) % N] += dp[k]
			next_dp[(10 * k + j) % N] %= mod
			
	dp = copy.copy(next_dp)
	
print(dp[5])

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
MOD = 1000000007


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

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

# dp
for i in range(1,len(S)):
  if S[i]=="?":
    ks = list(range(10))
  else:
    ks = [int(S[i])]
  for j in range(13):
    for k in ks:
      dp[i][(j*10+k)%13] = (dp[i][(j*10+k)%13]+dp[i-1][j]) % MOD
print(dp[len(S)-1][5])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for c in reversed(input()):
    x, y = (0, p * 10) if c == '?' else (p * int(c), p * int(c) + 1)
    a = [sum(a[(i - j) % 13] for j in range(x, y, p)) % M for i in range(13)]
    p = p * 10 % 13
print(a[5])

Submission status: Accepted

Solution code:
M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for c in reversed(input()):
    r = [x % 13 for x in range(0, p * 10, p)] if c == '?' else (p * int(c) % 13,)
    a = [sum(a[i - j] for j in r) % M for i in range(13)]
    p = p * 10 % 13
print(a[5])

Submission status: Accepted

Solution code:
M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for c in reversed(input()):
    r = range(0, p * 10, p) if c == '?' else (p * int(c),)
    if c != '?':
      a = [a[(i - p * int(c)) % 13] for i in range(13)]
    else:
      a = [sum(a[(i - j) % 13] for j in range(0, p * 10, p)) % M for i in range(13)] 
    p = p * 10 % 13
print(a[5])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
S = input()
# S = '?'*100000

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

for i in range(len(S)):
  nextdp = [0] * 13
  if S[i] == '?':
    for j in range(13):
      for k in range(10):
        nextdp[(j*10 + k)%13] += dp[j]
  else:
    for j in range(13):
      nextdp[(j*10 + int(S[i]))%13] += dp[j]
  for j in range(13):
    nextdp[j] %= num_mod
  dp = nextdp
  # print(dp)
print(dp[5])

Submission status: Accepted

Solution code:
s = input()
invs = s[::-1] # 逆向きの方がdpとの対応的にしっくりくるんやけど 

MOD = 10 ** 9 + 7
 
dp = [[0]*13 for _ in range(len(s))] #dp[桁][あまり] 

if invs[0]=='?':
    for i in range(10): # 0~9までは1 10~12は0のまま
        dp[0][i] = 1
else:
    dp[0][int(invs[0])] = 1

mul = 10 # 桁数のための変数 mul = 10 ** order
for order in range(1,len(s)):
    for j in range(13):
        if invs[order] == '?':
            for number in range(10):
                dp[order][ (j+number * mul )%13  ]  += dp[order-1][j]%MOD #いわゆる貰うdpで書いた
        else:
            number = int(invs[order])
            dp[order][(j+number * mul )%13 ]  += dp[order-1][j]%MOD
        dp[order][(j+number * mul )%13 ] %= MOD
    mul *= 10
    mul %= 13
print(dp[-1][5]%MOD)

# dpは基本的にpythonだと通らないからpypy3で提出するのを忘れないようにしよう...

Submission status: Accepted

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

dp[N][0] = 1
# DP = np.array(dp)
# print(DP)
mul = 1
for i in reversed(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][(j*mul+k)%13] += dp[i+1][k]
            dp[i][(j*mul+k)%13] %= mod
    mul *=10
    mul %=13

# DP = np.array(dp)
result = dp[0][5]
# print(DP)
print(result)

Submission status: Accepted

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


def main():
    s = input()[::-1]
    mod = 10 ** 9 + 7

    # DPテーブル（あまりが0～12となる組み合わせを管理）を用意
    n = 13
    dp = [0 for _ in range(n)]
    dp[0] = 1

    # 桁数の初期化
    digit = 1

    # 1文字ずつ見る
    for si in s:
        # 更新用のテーブルnext_dp[n]を用意
        next_dp = [0 for _ in range(n)]

        if si == '?':
            # '?'の取りうる範囲
            for q in range(10):
                # XXX: next_dpの括弧内の理解がかなり怪しい
                # digit - 1桁のときの結果を使って，
                # それぞれのあまりについて組み合わせの数を更新
                for j in range(n):
                    next_dp[(q * digit + j) % n] += dp[j]
                    next_dp[(q * digit + j) % n] %= mod
        else:
            q = int(si)

            for j in range(n):
                next_dp[(q * digit + j) % n] += dp[j]
                next_dp[(q * digit + j) % n] %= mod

        # DPテーブルを上書き
        dp = next_dp

        # 桁数を1つ増やす
        digit *= 10
        digit %= n

    # dp[5]が答え
    print(dp[5])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np


def solve(s):
    MOD = 10 ** 9 + 7
    dp = np.zeros(13, dtype=np.int64)
    dp[0] = 1
    idx = np.zeros(13, dtype=np.int8)
    for i in range(13):
        idx[i * 10 % 13] = i
    window = np.ones(10, dtype=np.int8)
    for c in s:
        if c == '?':
            tdp = dp[idx]
            ndp = np.concatenate([tdp[4:], tdp])
            dp = np.convolve(ndp, window, mode='valid') % MOD
        else:
            dp = np.roll(dp[idx], int(c))
    return dp[5]


s = input()
print(solve(s))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
# import numpy as np

S = input().rstrip()

MOD = 10 ** 9 + 7
n = len(S)

# dp = np.zeros((100005, 13), dtype=np.uint64)

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

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 ki in range(13):
            dp[i+1][(ki * 10 + j) %13] += dp[i][ki]
            
    for j in range(13):
        dp[i+1][j] %= MOD
        
        
    res = dp[n][5]
    
print(res)

Submission status: Accepted

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

cur = [0] * 13
cur[0] = 1
r = 1
for i in range(len(S)):
    s = S[-(i+1)]
    if s == '?':
        digits = range(10)
    else:
        digits = [int(s)]

    prev = cur
    cur = [0] * 13
    for m in range(13):
        for d in digits:
            cur[(m + r*d) % 13] += prev[m]
    for m in range(13):
        cur[m] %= MOD
    r = (10 * r) % 13

print(cur[5])

Submission status: Accepted

Solution code:
#from enum import Enum
#from queue import Queue
#import collections

#import sys
#import math
#import time

#t1=time.time()
#input = sys.stdin.readline
BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001


S = input().strip()
# S = str('?'*(10**5))
N = 13

dp =[0]*N
dp[0]=1

mul = 1
reversed_S = S[::-1]
for c in reversed_S:
    nextDP = [0]*N
    if c == '?':
        # print('test')
        # print(mul)
        for k in range(10):
            for j in range(N):
                nextDP[(mul*k+j)%N] += dp[j]
                nextDP[(mul*k+j)%N] %= MOD
    else:
        k = int(c)
        for j in range(N):
            nextDP[(mul*k+j)%N] += dp[j]
            nextDP[(mul*k+j)%N] %= MOD

    mul *= 10
    mul %= N
    dp = nextDP[:]
print(dp[5])
#print(time.time()-t1)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7


def main():
    S = input()

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

    for i, s in enumerate(S):
        c = int(s) if s != '?' else -1

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

        for j, v in enumerate(dp[i + 1]):
            dp[i + 1][j] = v % MOD

    print(dp[-1][5])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

MOD = 10 ** 9 + 7
S = input().rstrip()

ten = np.zeros(13, dtype=np.uint64)
ten[:10] += 1
add_all = [ten]
for _ in range(5):
  add_all.append(add_all[-1][np.arange(0,52,4)%13])

add_single = [[x * 10 ** i for x in range(10)] for i in range(6)]

add_all_count = [0] * 6
constant_term = 0
for i,s in enumerate(S[::-1]):
  if s == '?':
    add_all_count[i%6] += 1
  else:
    constant_term += add_single[i%6][int(s)]

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

def nth_convolve(arr,n):
  if n == 1:
    return arr
  x = nth_convolve(arr,n>>1)
  x = convolve(x,x)
  return convolve(arr,x) if n & 1 else x

dp = np.zeros(13, dtype=np.uint64)
dp[constant_term % 13] = 1
for arr,n in zip(add_all, add_all_count):
  if n > 0:
    dp = convolve(dp, nth_convolve(arr,n))

print(dp[5])

Submission status: Accepted

Solution code:
#printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)


rem = [1,10,9,12,3,4]
s = input().strip()
sr = s[::-1]
n = len(s)
dp = [ [0]*13 for i in range(n) ]
if sr[0]=='?':
    for j in range(10):
        dp[0][j] = 1
else:
    j = int(sr[0])
    dp[0][j] = 1

for i in range(1,n):
    r = rem[i%6]
    if sr[i]=='?':
        for j in range(10):
            for k in range(13):
                dp[i][(k+j*r)%13] = (dp[i][(k+j*r)%13] + dp[i-1][k])%R
    else:
        j = int(sr[i])
        for k in range(13):
                dp[i][(k+j*r)%13] = (dp[i][(k+j*r)%13] + dp[i-1][k])%R

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

MOD = 10 ** 9 + 7
S = input().rstrip()

ten = np.zeros(13, dtype=np.int64)
ten[:10] += 1
add_all = [ten]
for _ in range(5):
  add_all.append(add_all[-1][np.arange(0,52,4)%13])

add_single = [[x * 10 ** i for x in range(10)] for i in range(6)]

add_all_count = [0,0,0,0,0,0]
constant_term = 0
for i,s in enumerate(S[::-1]):
  if s == '?':
    add_all_count[i%6] += 1
  else:
    constant_term += add_single[i%6][int(s)]

def convolve(x,y):
  z = np.zeros(25,dtype=np.int64)
  for i in range(13):
    z[i:i+13] += x[i] * y % MOD
  z[:12] += z[13:25]
  return z[:13] % MOD

def nth_convolve(arr,n):
  if n == 0:
    x = np.zeros(13, dtype=np.int64)
    x[0] = 1
    return x
  if n == 1:
    return arr
  x = nth_convolve(arr,n>>1)
  x = convolve(x,x)
  return convolve(arr,x) if n & 1 else x

dp = np.zeros(13, dtype=np.int64)
dp[constant_term % 13] = 1
for arr,n in zip(add_all, add_all_count):
  dp = convolve(dp, nth_convolve(arr,n))

print(dp[5])

Submission status: Accepted

Solution code:
S = [int(x) if x != "?" else -1 for x in input()]
g = 10 ** 9 + 7
x = 1
DP = [[0] * 13 for _ in range(2)]
DP[0][0] = 1
for i in range(len(S)):
    DP[1], DP[0] = DP[0], DP[1]
    for j in range(13):
        DP[0][j] = 0
    for j in range(13):
        if S[i] == -1:
            s = (j*10)%13
            e = (s+10)%13
        else:
            s = (j*10+S[i])%13
            e = (s+1)%13
        DP[0][s] += DP[1][j]
        if s > e:
            DP[0][0] += DP[1][j]
        DP[0][e] -= DP[1][j]
    w = 0
    for j in range(13):
        w = (w + DP[0][j]) % g
        DP[0][j] = w

print(DP[0][5] % g)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
 
s= sys.stdin.readline().strip()
#
MOD=10**9+7
mmap= []
for i in range(6):
    b = 10**i % 13
    mmap.append( [ [ (b*i+j)%13 for i in range(1,10) ] for j in range(13) ] )
#
dp= [ 0 ] * 13
dp[0] = 1
j= 0
for c in reversed(s):
    tmp = dp.copy()
    #
    if c=="0": pass
    elif c=="?":
        bset = mmap[j]
        for m,num in enumerate(tmp):
            if num==0: continue
            for idx in bset[m]: dp[idx]+=num
        #
        for i in range(13): dp[i]%=MOD
    else:
        b= mmap[j][0][int(c)-1]
        for m in range(13):
            idx= (m+b)%13
            dp[idx]= tmp[m]
    #
    if j==5: j=0
    else: j+=1
#
print(dp[5])

Submission status: Accepted

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

dp = np.zeros(13, dtype = np.int64)
dp[0] = 1

move = np.arange(0,52,4) % 13
ten = np.ones(10, dtype=np.int64)
for s in input():
  dp = dp[move]
  if s == '?':
    dp = np.convolve(dp, ten)
    dp[:9] += dp[13:22]
    dp %= MOD
  else:
    dp = np.roll(dp, int(s))
  
print(dp[5])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC135 D

import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7

s = list(input())
s = s[::-1]
l = len(s)
#dp[i][j] := 先頭i文字として考えられるもののうち、13で割ったあまりがjであるもの
dp = [[0]*13 for _ in range(l)]
remain = 1
if s[0] == '?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(s[0])] = 1

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

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

S = input()
N = len(S)

# dp[i][k]: i桁目までのkで割った余りの数
dp = create_grid(N+1, 13)

dp[0][0] = 1 # 0桁目

s = [1]
for i in range(N):
  s.append((s[-1]*10)%13)

for i in range(N):
    c = S[N-i-1]
    if c == "?":
        v = range(10)
    else:
        v = [int(c)]
    for vi in v:
        for j in range(13):
            amari = (vi*s[i] + j) % 13
            dp[i+1][amari] = (dp[i][j] + dp[i+1][amari]) % MOD

print(dp[N][5])

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