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
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):
        if S[j - 1] == "?":
            for k in range(13):
                for q in range(10):
                    new_k = (k * 10 + q) %13
                    dp[j][new_k] += dp[j - 1][k]
            for k in range(13):
                dp[j][k] %= mod
        else:
            n = int(S[j - 1])
            for k in range(13):
                new_k = (k * 10 + n)%13
                dp[j][new_k] += dp[j - 1][k]
                dp[j][new_k] %= mod
    print(dp[l][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):
        if S[j - 1] == "?":
            for k in range(13):
                for q in range(10):
                    new_k = (k * 10 + q) %13
                    dp[j][new_k] += dp[j - 1][k]
                    dp[j][new_k] %= mod
        else:
            n = int(S[j - 1])
            for k in range(13):
                new_k = (k * 10 + n)%13
                dp[j][new_k] += dp[j - 1][k]
                dp[j][new_k] %= mod
    print(dp[l][5])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
S = input()
N = len(S)
dp = []
for _ in range(N+1):
    dp.append([0] * 13)
dp[0][0] = 1
p = 10**9+7

for i in range(1, N+1):
    X = S[N-i]
    if X == '?':
        for j in range(10):
            X = (j * pow(10, i-1, 13)) % 13
            for k in range(13):  # 上段の各あまりに対して、xのあまりを加える
                Y = dp[i-1][k]
                Z = (X + k) % 13  # 新たなあまり
                dp[i][Z] += Y % p

    else:
        X = int(X)
        X = (X * pow(10, i-1, 13)) % 13
        for k in range(13):  # 上段の各あまりに対して、xのあまりを加える
            Y = dp[i-1][k]
            Z = (X + k) % 13  # 新たなあまり
            dp[i][Z] += Y % p

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

Submission status: Accepted

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

for i in range(1,N+1):
    X = S[N-i]
    if X=="?":
        for X in range(10):
            Y = (X*pow(10,i-1,13))%13
            for j in range(13):
                if 0<=Y+j<=12:
                    Z = Y+j
                else:
                    Z = Y+j-13
                dp[i][Z] = (dp[i][Z]+dp[i-1][j])%p
    else:
        X = int(X)
        Y = (X*pow(10,i-1,13))%13
        for j in range(13):
            if 0<=Y+j<13:
                Z = Y+j
            else:
                Z = Y+j-13
            dp[i][Z] = dp[i-1][j]
#print(*dp,sep='\n')
print(dp[-1][5])

Submission status: Accepted

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

t = [[0 for j in range(13)] for i in range(n)]
for i,x in enumerate(s):
    A = pow(10, i ,13)
    if i == 0:
        if x == "?":
            for j in range(0,10):
                t[i][j] += 1
        else:
            t[i][int(x)] += 1
    else:
        if x == "?":
            for k in range(13):
                for j in range(10):
                    b = (k + j*A)%13
                    t[i][b] += t[i-1][k]
                    t[i][b] %= mod
        else:
            for k in range(0,13):
                b = (k + int(x)*A)%13
                t[i][b] += t[i-1][k]
                t[i][b] %= mod
print(t[-1][5]%mod)

Submission status: Accepted

Solution code:
from collections import defaultdict

S = input()
N = len(S)

MOD = 10**9 + 7
mod = 13

A = [1, 10, 9, 12, 3, 4]
D = defaultdict(int)
a = 0

for i in range(N):
  if S[-1-i] == "?":
    D[A[i%6]] += 1
  else:
    a += A[i%6] * int(S[-1-i]) % mod
    a %= mod

ans = [0]*mod
ans[0] = 1

for i, x in D.items():
  for _ in range(x):
    prev = [a for a in ans]
    ans = [0]*mod
    for j in range(mod):
      for y in range(10):
        ans[(j+i*y)%mod] += prev[j]
      ans = [a%MOD for a in ans]

print(ans[(5-a)%mod])

Submission status: Accepted

Solution code:
def main():
  s = input()
  mod = 10**9+7
  dp = [0]*13
  dp[0] = 1
  digit = 1
  for i in range(len(s)):
    nextDP = [0]*13
    if s[i] == "?":
      for k in range(10):
        for j in range(13):
          t = (k + j * 10)%13
          nextDP[t] = (dp[j] + nextDP[t]) % mod
    else:
      si = int(s[i])
      for j in range(13):
        t = (si + j * 10)%13
        nextDP[t] = (dp[j] + nextDP[t]) % mod
    dp = nextDP
    digit *= 10
  print(dp[5])

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys, math
from collections import defaultdict
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

S = rs()

L = len(S)

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

R = [0]*L
d = 1
for i in range(L):
	d %= 13
	R[i] = d
	d *= 10
R.reverse()

dp[0][0] = 1

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod=10**9+7
s=input()[::-1]
l=len(s)
dp=[[0]*13 for i in range(l+1)]
dp[0][0]=1
#累乗が大きすぎるので前計算
p=[0]*l
p[0]=1
for i in range(l-1):
    p[i+1]=(p[i]*10)%13
for i in range(l):
    s_sub=s[i]
    if s_sub=="?":
        for j in range(13):
            for k in range(10):
                dp[i+1][(j+k*p[i])%13]+=dp[i][j]
                dp[i+1][(j+k*p[i])%13]%=mod
    else:
        k=int(s_sub)
        for j in range(13):
            dp[i+1][(j+k*p[i])%13]+=dp[i][j]
            dp[i+1][(j+k*p[i])%13]%=mod
print(dp[l][5])

Submission status: Accepted

Solution code:
S=input()
N=len(S)
mod=10**9+7
DP=[[0]*13 for i 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):
        DP[i+1][(j*10+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*10+int(S[i]))%13]=DP[i][j]
print(DP[N][5])

Submission status: Accepted

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

if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
mod1,mod2=10**9+7,998244353
mod=mod1
dp=[0]*13
dp[0]=1
for i in input():
    if i=="?":
        dp=[sum(dp[4*(j-k)%13]for k in range(10))%mod for j in range(13)]
    else:
        x=int(i)
        dp=[dp[4*(j-x)%13]for j in range(13)]
    
    #print(dp)
print(dp[5])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    s = input()
    n = len(s)
    m13 = [0,10,7,4,1,11,8,5,2,12,9,6,3]
    dp = [0]*13
    mod = 10**9+7
    dp[0] = 1
    for i in s:
        dpp = dp*1
        if i == "?":
            dp = [0]*13
            for j in range(13):
                for k in range(10):
                    nj = m13[j]+k
                    dp[(m13[j]+k)%13] = (dp[(m13[j]+k)%13]+dpp[j])%mod
        else:
            ii = int(i)
            for j in range(13):
                dp[(m13[j]+ii)%13] = dpp[j]
    print(dp[5])
    return

if __name__ == '__main__':
    main()

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 num in range(0,9+1):
                dp[i+1][(j*10+num)%13] += dp[i][j]
                dp[i+1][(j*10+num)%13]%=MOD
    else:
        num = int(s[i])
        for j in range(13):
            dp[i+1][(j*10+num)%13] += dp[i][j]
            dp[i+1][(j*10+num)%13]%=MOD

print(dp[n][5])

Submission status: Accepted

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

mod = 10**9+7
dp[0][0] = 1

for i in range(len(s)):
  for j in range(10): #j=今見ている桁の数字
    if s[i] != "?" and int(s[i]) != j:
      continue
    for k in range(13): #k=一桁前までのあまり
      dp[i+1][(j+10*k)%13] += dp[i][k]
      dp[i+1][(j+10*k)%13] %= mod
      
print(dp[-1][5])

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

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

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

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

S = S()
N = len(S)
dp = [[0 for j in range(13)] for i in range(N+1)]
dp[0][0] = 1
for i in range(N):
  s = S[N-1-i]
  p = pow(10,i,13)
  if s=="?":
    for j in range(13):
      for k in range(10):
        dp[i+1][j] += dp[i][(j-k*p)%13]
        dp[i+1][j] %= MOD
  else:
    s = int(s)
    for j in range(13):
      dp[i+1][j] = dp[i][(j-s*p)%13]
      dp[i+1][j] %= MOD
      
print(dp[-1][5])

Submission status: Accepted

Solution code:
S = input()

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

Submission status: Accepted

Solution code:
S = str(input())

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

mod = 1000000007

for i in range(len(S)):
    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] = Dp[i+1][j]%mod
        
print(Dp[-1][5])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

S = readline().rstrip()
S = S[::-1]
dp = [0]*13
dp[0] = 1
pow10 = 4
for i,s in enumerate(S):
    dpnew = [0]*13
    pow10 = (pow10*10)%13
    if s != '?':
        k = int(s)
        for j in range(13):
            dpnew[(k*pow10+j)%13] = (dpnew[(k*pow10+j)%13]+dp[j])%mod
    else:
        for k in range(10):
            for j in range(13):
                dpnew[(k*pow10+j)%13] = (dpnew[(k*pow10+j)%13]+dp[j])%mod
    dp = dpnew

print(dp[5])

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

S = readline().rstrip()
S = S[::-1]
dp = [0]*13
dp[0] = 1

for i,s in enumerate(S):
    dpnew = [0]*13
    pow10 = pow(10,i,13)
    if s != '?':
        k = int(s)
        for j in range(13):
            dpnew[(k*pow10+j)%13] = (dpnew[(k*pow10+j)%13]+dp[j])%mod
    else:
        for k in range(10):
            for j in range(13):
                dpnew[(k*pow10+j)%13] = (dpnew[(k*pow10+j)%13]+dp[j])%mod
    dp = dpnew

print(dp[5])

Submission status: Accepted

Solution code:
from sys import stdin
s = stdin.readline()[:-1]

length = len(s)

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

s = list(reversed(s))

dp[0][0]=1
ten = 1
mod = 1000000007


for i in range(length):
	if s[i] == '?':
		for num in range(10):
			d = num*ten
			for j in range(13):
				k = (j+d)%13
				dp[i+1][k] += dp[i][j]
				dp[i+1][k] %= mod
	else:
		num = int(s[i])
		d = num*ten
		for j in range(13):
			k = (j+d)%13
			dp[i+1][k] += dp[i][j]
			dp[i+1][k] %= mod
	ten *= 10
	ten %= 13

print(int(dp[length][5]%mod))

Submission status: Accepted

Solution code:
MOD = 10**9+7

s = str(input())

dp = [ [0]*13 for _ in range(len(s)+1) ]
dp[0][0] = 1
# if s[0] == '?':
#     dp[]

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

print(dp[-1][5])

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
mod = 10**9+7

S = s()
N = len(S)
dp = [[0]*13 for _ 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][(10*j+k)%13] = (dp[i+1][(10*j+k)%13]+dp[i][j])%mod
        else:
            x = int(S[i])
            dp[i+1][(10*j+x)%13] = (dp[i+1][(10*j+x)%13]+dp[i][j])%mod
print(dp[N][5])

Submission status: Accepted

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

# dp[i][r] = (最初のi桁を見て、余りがrとなるような個数)
dp = [[0] * 13 for _ in range(n + 1)]
dp[0][0] = 1

for i in range(n):
    if s[i] == '?':
        for r in range(13):
            for d in range(10):
                r1 = (r * 10 + d) % 13
                dp[i + 1][r1] += dp[i][r]
                dp[i + 1][r1] %= MOD
    else:
        for r in range(13):
            r1 = (r * 10 + int(s[i])) % 13
            dp[i + 1][r1] += dp[i][r]
            dp[i + 1][r1] %= MOD

ans = dp[n][5]
# print(*dp, sep='\n')
print(ans)

Submission status: Accepted

Solution code:
S = input()
MOD = 10**9+7
N = 13
mul = 1

#dp[k] -> 13で割ったあまりがkのパターン数
dp = [0] * N
dp[0] = 1

#後ろから解くアルゴリズム
# 1?2?3 : 0 -> 3 -> ?3 -> 2?3 -> ...
for i in range(len(S)-1, -1, -1):
    #次の状態
    next_dp = [0] * N
    c = S[i]

    if c == "?":
        for k in range(10):
            for j in range(N):
                next_dp[(k * mul + j) % N] += dp[j]
                next_dp[(k * mul + j) % N] %= MOD

    else:
        k = int(S[i])
        for j in range(N):
            next_dp[(k * mul + j) % N] += dp[j]
            next_dp[(k * mul + j) % N] %= MOD

    mul *= 10
    mul %= N
    dp = next_dp

print(dp[5])

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    S = readline().strip()
    S = S[::-1]

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

    for i, c in enumerate(S):
        dp, dp_prev = [0] * 13, dp
        for k in range(13):
            if c == '?':
                for j in range(10):
                    dp[(p * j + k) % 13] = (dp[(p * j + k) % 13] + dp_prev[k]) % MOD
            else:
                dp[(p * int(c) + k) % 13] = (dp[(p * int(c) + k) % 13] + dp_prev[k]) % MOD

        p = p * 10 % 13

    print(dp[5])
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    S = readline().strip()
    N = len(S)
    power = [0] * N
    power[0] = 1
    for i in range(N - 1):
        power[i + 1] = 10 * power[i] % 13

    S = S[::-1]

    Q = []
    const = 0
    for i, c in enumerate(S):
        if c == '?':
            Q.append(i)
        else:
            const = (const + power[i] * int(c)) % 13

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

    for i in range(len(Q)):
        dp, dp_prev = [0] * 13, dp
        p = power[Q[i]]
        for j in range(10):
            for k in range(13):
                idx = (p * j + k) % 13
                dp[idx] = (dp[idx] + dp_prev[k]) % MOD

    print(dp[5])
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    S = readline().strip()
    N = len(S)
    power = [0] * N
    power[0] = 1
    for i in range(N - 1):
        power[i + 1] = 10 * power[i] % 13

    S = S[::-1]

    Q = [i for i, c in enumerate(S) if c == '?']
    M = len(Q)

    const = 0
    for i, c in enumerate(S):
        if c != '?':
            const = (const + power[i] * int(c)) % 13

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

    for i in range(M):
        dp, dp_prev = [0] * 13, dp
        p = power[Q[i]]
        for j in range(10):
            for k in range(13):
                idx = (p * j + k) % 13
                dp[idx] = (dp[idx] + dp_prev[k]) % MOD

    print(dp[5])
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
s = input()
 
mod = 10**9+7
n = len(s)
res = [1] + [0] * 12
for ss in s:
    dp = [0] * 13
    for i in range(13):
        dp[(10*i)%13] = res[i]
    dp += dp
 
    if ss == '?':
        for i in range(13):
            res[i] = sum(dp[i+4:i+14])
    else:
        for i in range(13):
            res[i] = dp[i+13-int(ss)]
    res = [v%mod for v in res]
print(res[5])

Submission status: Accepted

Solution code:
#

import sys
input=sys.stdin.readline

def main():
    MOD=10**9+7
    S=input().strip("\n")
    q=[]
    g=0
    S=S[::-1]
    m13=(1,10,9,12,3,4)
    for i in range(len(S)):
        if S[i] == "?":
            q.append(m13[i%6])
        else:
            x=int(S[i])
            g+=x*m13[i%6]
            g%=13
    if len(q)==0:
        if g==5:
            print(1)
        else:
            print(0)
        exit()
    N=len(q)
    q=[0]+q
    dp=[[0]*13 for i in range(N+1)]
    for j in range(10):
        dp[1][(j*q[1])%13]=1
    for i in range(2,N+1):
        for j in range(13):
            for k in range(10):
                x=(j-k*q[i])%13
                dp[i][j]+=dp[i-1][x]
                dp[i][j]%=MOD
    print(dp[N][(5-g)%13])
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo


@mt
def slv(S):
    memo = [0] * 13
    memo[0] = 1
    mod = 10**9 + 7
    for c in S:
        nm = [0] * 13
        if c == '?':
            r = range(10)
        else:
            r = [int(c)]
        for d in r:
            for i in range(13):
                nm[(i*10+d) % 13] += memo[i]
                nm[(i*10+d) % 13] %= mod
        memo = nm
    return memo[5]


def main():
    S = read_str()
    print(slv(S))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
 
MOD = 1000000007  # type: int
 
 
def solve(S: str):
    """
    >>> solve("05")
    1
    >>> solve("18")
    1
    >>> solve("13")
    0
    """
    pre, cur = [0] * 13, None
    base = 10
    if S[-1] == "?":
        cur = [1] * 10 + [0] * 3
    else:
        cur = [0] * 13
        cur[int(S[-1])] = 1
    for n in reversed(S[:-1]):
        pre, cur = cur, pre
        for i in range(13): # 再生成を避ける
            cur[i] = 0
        g = range(10) if n == "?" else [int(n)]
        for i in g:
            t = base * i % 13
            for j in range(13):
                cur[(j+t)%13] = (cur[(j+t)%13] + pre[j]) % MOD
        base = (base * 10) % 13        
        # print(n, pre, cur, base)
    return cur[5]
 
# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    print(solve(S))
 
def test():
    import doctest
    doctest.testmod()
 
if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
s = input()

mod = 10**9+7
n = len(s)
res = [1] + [0] * 12
for ss in s:
    dp = [0] * 13
    for i in range(13):
        dp[(10*i)%13] = res[i]
    dp += dp

    if ss == '?':
        for i in range(13):
            res[i] = sum(dp[i+4:i+14])
    else:
        for i in range(13):
            res[i] = dp[i+13-int(ss)]
    res = [v%mod for v in res]
print(res[5])

Submission status: Accepted

Solution code:
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():

    s = str(input())
    ls = len(s)
    dp = [[0]*13 for _ in range(ls+1)]
    dp[0][0] = 1
    MOD = 10**9+7

    for i in range(ls):
        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[ls][5])


resolve()

Submission status: Accepted

Solution code:
S = input()[::-1]
L = len(S)
MOD = 10**9+7
N = 13
# 0~13
dp = [ [0]*13 for i in range(L+1)]
dp[0][0] = 1
mul = 1

for i in range(L):
  if S[i] == "?":
    for prev in range(N):
      for j in range(10):
        dp[i+1][(j*mul+prev)%N] += dp[i][prev]
        dp[i+1][(j*mul+prev)%N] %= MOD
  else:
    j = int(S[i])
    for prev in range(N):
      dp[i+1][(j*mul+prev)%N] += dp[i][prev]
      dp[i+1][(j*mul+prev)%N] %= MOD
  
  mul *= 10
  mul %= N

print(dp[-1][5])

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np
def main():
    #入力
    readline=stdin.readline
    mod=10**9+7
    s=readline().strip()
    n=len(s)

    convert=[[0]*13 for i in range(13)]
    for a in range(13):
        for b in range(10):
            convert[a][(10*a+b)%13]=1

    convert=np.array(convert,dtype=np.int64)
    dp=np.zeros(13,dtype=np.int64)
    dp[0]=1
    for i in range(n):
        if s[i]=="?":
            tmp=np.dot(dp,convert)
        else:
            x=int(s[i])
            tmp=np.zeros(13,dtype=np.int64)
            for j in range(13):
                tmp[(j*10+x)%13]=dp[j]
        tmp%=mod
        dp=tmp

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

Submission status: Accepted

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

mod = 10**9 + 7

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

for i in range(1, N+1):
    if S[i-1] == "?":
        for j in range(10):
            tmp_mod = (j * pow(10, i-1, 13)) % 13
            for k in range(13):
                dp[i][k] = (dp[i][k] + dp[i-1][k-tmp_mod%13]) % mod

    else:
        tmp_mod = (int(S[i-1]) * pow(10, i-1, 13)) % 13
        for k in range(13):
            dp[i][k] = (dp[i][k] + dp[i-1][k-tmp_mod%13]) % mod

print(dp[N][5])