Problem:


Score : 400 points

Problem Statement

Given is a string S. Each character in S is either a digit (0, ..., 9) or ?.

Among the integers obtained by replacing each occurrence of ? with a digit, how many have a remainder of 5 when divided by 13? An integer may begin with 0.

Since the answer can be enormous, print the count modulo 10^9+7.

Constraints

S is a string consisting of digits (0, ..., 9) and ?.

1 \leq |S| \leq 10^5

Input

Input is given from Standard Input in the following format:

S

Output

Print the number of integers satisfying the condition, modulo 10^9+7.

Sample Input 1

??2??5

Sample Output 1

768

For example, 482305, 002865, and 972665 satisfy the condition.

Sample Input 2

?44

Sample Output 2

1

Only 044 satisfies the condition.

Sample Input 3

7?4

Sample Output 3

0

We may not be able to produce an integer satisfying the condition.

Sample Input 4

?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76???

Sample Output 4

153716888



Sample input:
??2??5


Sample output:
768

Submission status: Accepted

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

res_dic = {}
for i in range(13):
    if (i*10)%13 in res_dic:
        res_dic[(i*10)%13].append(i)
    else:
        res_dic[(i*10)%13] = [i]
        
caseq_list = [[0 for j in range(13)] for i in range(10)]
for num in range(10):
    for j in range(13):
        k = (j - num)%13
        if k in res_dic:
            for m in res_dic[k]:
                caseq_list[num][j] = m
        
dp = [[0 for j in range(13)] for i in range(n+1)]    # i番目までの文字を読み込んだ時に13で割った余りがjになる数の個数
if s[0] == '?':
    for i in range(10):
        dp[1][i] =  1
else:
    num = ord(s[0]) - ord('0')
    dp[1][num] = 1

for i in range(1,n):
    c = s[i]
    if c == '?':
        for num in range(10):
            for j in range(13):
                dp[i+1][j] = (dp[i+1][j] + dp[i][caseq_list[num][j]]) % MOD
    else:
        num = ord(c) - ord('0')
        for j in range(13):
            dp[i+1][j] = (dp[i+1][j] + dp[i][caseq_list[num][j]]) % MOD
print(dp[n][5])

Submission status: Accepted

Solution code:
def STR(): return input()

mod = 1000000007

s = STR()
l = len(s)
dp = [[0] * 13 for _ in range(l + 1)] #dp[i]i桁目まで決めた時の13で割ったあまりが[j]の個数
dp[0][0] = 1


for i in range(l + 1): #i桁目まで決める
    if s[i-1] == '?':
        for j in range(13): #i-1桁目のあまりがj
            a = dp[i-1][j]
            b = j * 10
            for k in range(10): #i桁目の値
                dp[i][(b + k) % 13] += a
        for j in range(13):
            dp[i][j] %= mod
    else:
        a = int(s[i-1])
        for j in range(13): #i-1桁目のあまりがj
            num = (j * 10 + a) % 13
            dp[i][num] += dp[i-1][j]
            dp[i][num] %= mod
#print(dp)
print(dp[l][5])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines 
MOD = 10**9+7

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

mul = 1
for n in range(N):
    s = S[-(n+1)] # 後方から
    if s == "?":
        for i in range(10):
            for mo in range(13):
                ind = (i * mul + mo) % 13
                dp[n+1][ind] += dp[n][mo]
                dp[n+1][ind] %= MOD
    else:
        i = int(S[-(n+1)])
        for mo in range(13):
            ind = (i * mul + mo) % 13
            dp[n+1][ind] += dp[n][mo]
            dp[n+1][ind] %= MOD
    mul *= 10
    mul %= 13

print(dp[N][5])

Submission status: Accepted

Solution code:
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def modinv(a, m):
    g, x, y = xgcd(a, m)
    return x % m
def main():
    s=list(input())
    mod=10**9+7
    K=modinv(10,13)
    U=[[0 for i in range(10) ]for k in range(13)]
    for i in range(13):
        for j in range(10):
            U[i][j]=((i-j)*K)%13

    dp=[[0 for k in range(13)] for i in range(len(s))]
    #dp[i][j]=初めのindex=i番目まで見たときに、あまりがjになるような方法の総数
    num=s[0]
    if s[0]=="?":
        for i in range(10):
            dp[0][i]=1
    else:
        number=int(s[0])
        dp[0][number]=1

    for i in range(1,len(s)):
        for k in range(13):
            if s[i]=="?":
                for j in range(10):
                    dp[i][k]+=dp[i-1][U[k][j]]%mod
            else:
                number=int(s[i])
                dp[i][k]=dp[i-1][U[k][number]]%mod
    print(dp[len(s)-1][5]%mod)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import pow
S = input()
S = list(S)
S.reverse()
l = len(S)
dp =[ [0] * 13 for _ in range(l + 1)]
dp[0][0] = 1
MOD = 10 ** 9 + 7
keta = 1
for k,c in enumerate(S):
    if c == "?":
        for i in range(0,10): # ? に入る候補達
            for amari in range(0, 13):
                next_amari = (amari + i * keta ) % 13
                dp[k + 1][next_amari] += (dp[k][amari] )
                dp[k + 1][next_amari] %= MOD
    else:
        i = int(c)
        for amari in range(0,13):
            next_amari = (amari + i * keta ) % 13
            dp[k + 1][ next_amari] += (dp[k][amari])
            dp[k + 1][next_amari] %= MOD

    keta *= 10
    keta %= 13

print(dp[l][5])

Submission status: Accepted

Solution code:
M=10**9+7
r=[[(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])

Submission status: Accepted

Solution code:
#import numpy as np
def main():
    S=input()
    #dp=np.zeros((len(S)+1,13),dtype=int)
    dp=[[0]*13 for _ in range(len(S)+1)]
    dp[0][0]=1
    mod=10**9+7
    """
    for i in range(1,len(S)+1):
        for a in range(13):
            if S[i-1]=="?":
                if a*10%13<(a*10+10)%13:
                    dp[i][a*10%13:(a*10+10)%13]+=dp[i-1][a]
                    dp[i][a*10%13:(a*10+10)%13]%=mod
                else:
                    dp[i][a*10%13:]+=dp[i-1][a]
                    dp[i][a*10%13:]%=mod
                    dp[i][:(a*10+10)%13]+=dp[i-1][a]
                    dp[i][:(a*10+10)%13]%=mod
            else:
                dp[i][(a*10+int(S[i-1]))%13]+=dp[i-1][a]
                dp[i][(a*10+int(S[i-1]))%13]%=mod
    print(dp[len(S)][5])
"""
    for i in range(1,len(S)+1):
        for a in range(13):
            if S[i-1]=="?":
                for n in range(10):
                    dp[i][(a*10+n)%13]+=dp[i-1][a]
                    dp[i][(a*10+n)%13]%=mod
            else:
                dp[i][(a*10+int(S[i-1]))%13]+=dp[i-1][a]
                dp[i][(a*10+int(S[i-1]))%13]%=mod
    print(dp[len(S)][5])
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
s = list(input())
s.reverse()
n = len(s)
mod = 10**9+7
#dp[i][j] := 下からi桁目まで決めたとき、13で割った余りがjの個数
dp = [[0 for i in range(13)] for j in range(n+1)]
dp[0][0] = 1
cur = 1
for i in range(n):
    for j in range(13):
        char = s[i]
        if char == '?':
            for k in range(10):
                #i+1桁目をkにする
                tmp = (k * cur) % 13
                dp[i+1][(j + tmp) % 13] += dp[i][j]
                dp[i+1][(j + tmp) % 13] %= mod
        else:
            x = int(char)
            tmp = (x * cur) % 13
            dp[i+1][(j + tmp) % 13] += dp[i][j]
            dp[i+1][(j + tmp) % 13] %= mod
    cur = (cur * 10) % 13
print(dp[n][5])

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

MAX = 10**9 + 7

def main():
  s = input().strip()
  p = 13
  dp = [[0]*p for _ in range(len(s))]
  remains = [[0]*p for _ in range(6)]
  for i in range(6):
    for j in range(p):
      remains[i][j] = ((10 ** i) * j) % p
    
  if s[-1] == '?':
    dp[0][:10] = [1] * 10
  else:
    dp[0][int(s[-1])] = 1
    
  for i, c in enumerate(s[::-1][1:], 1):
    if c == '?':
      for c in range(10):
        for j in range(p):
          dp[i][(remains[i%6][c] + j) % p] += (dp[i-1][j] % MAX) 
    else:
      c = int(c)
      for j in range(p):
        dp[i][(remains[i%6][c] + j) % p] += (dp[i-1][j] % MAX) 
        
  print(dp[-1][5] % MAX)
  
if __name__=='__main__':
  main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

    @staticmethod
    def divisor(n):
        i = 1
        table = []
        while i * i <= n:
            if n % i == 0:
                table.append(i)
                table.append(n // i)
            i += 1
        table = list(set(table))
        return table


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)

    def list(self):
        return self.__q

    def length(self):
        return len(self.__q)


sys.setrecursionlimit(1000000)
MOD = int(1e09) + 7
INF = int(1e30)


def main():
    # sys.stdin = open("Sample.txt")
    S = Scanner.string()
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(N):
        c = S[i]
        if c == "?":
            for k in range(10):
                for j in range(13):
                    dp[i+1][(j * 10 + k) % 13] += dp[i][j]
                    dp[i+1][(j * 10 + k) % 13] %= MOD
        else:
            k = int(S[i])
            for j in range(13):
                dp[i+1][(j * 10 + k) % 13] += dp[i][j]
                dp[i+1][(j * 10 + k) % 13] %= MOD
    print(dp[N][5])
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
S=input()
N=len(S)
count=0
hatenadata=[]
Sinfo=[]
for i in range(0,N):
    if S[i]=='?':
        Sinfo.append('0')
        count+=1
        hatenadata.append(i)
    else:
        Sinfo.append(S[i])
X=''.join(Sinfo)
first=int(X)%13

dp=[[0 for i in range(0,13)] for i in range(0,count+1)]

for i in range(0,13):
    if first==i:
        dp[0][i]=1

for i in range(1,count+1):
    digit=N-hatenadata[i-1]
    for j in range(0,13):
        dp[i][j]=sum(dp[i-1][(j-k*10**((digit-1)%6))%13] for k in range(0,10))%(10**9+7)

print(dp[count][5]%(10**9+7))

Submission status: Accepted

Solution code:
MOD = 10**9+7
# dp[i][j] := Sの後ろからi桁を13で割った余りがjとなるようなものの個数
S = input()
l = len(S)
dp = [[0]*13 for _ in range(l+5)]
dp[0][0] = 1
mul = 1  
for i in range(l):
    x = S[-(i+1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= MOD
    else:
        k = int(x) # これしか選ぶ余地なし
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= MOD
    mul = mul * 10 % 13
print(dp[l][5]%MOD)

Submission status: Accepted

Solution code:
MOD = 10**9+7
# dp[i][j] := Sの後ろからi桁を13で割った余りがjとなるようなものの個数
S = input()
l = len(S)
dp = [[0]*13 for _ in range(l+5)]
dp[0][0] = 1
mul = 1

for i in range(l):
    x = S[-(i+1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= MOD
    else:
        k = int(x) # これしか選ぶ余地なし
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= MOD
    mul = mul * 10 % 13
print(dp[l][5]%MOD)

Submission status: Accepted

Solution code:
MOD = 10**9+7
# dp[i][j] := Sの後ろからi桁を13で割った余りがjとなるようなものの個数
S = input()
l = len(S)
dp = [[0]*13 for _ in range(l+5)]
dp[0][0] = 1
mul = 1

for i in range(l):
    x = S[-(i+1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= MOD
    else:
        k = int(x) # これしか選ぶ余地なし
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= MOD
    mul = mul * 10 % 13
print(dp[len(S)][5]%MOD)

Submission status: Accepted

Solution code:
MOD = 10**9+7
# dp[i][j] := Sの後ろからi桁を13で割った余りがjとなるようなものの個数
S = input()
l = len(S)
dp = [[0]*13 for _ in range(l+1)]
dp[0][0] = 1
mul = 1

for i in range(l):
    x = S[-(i+1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= MOD
    else:
        k = int(x) # これしか選ぶ余地なし
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= MOD
    mul = mul * 10 % 13
print(dp[len(S)][5]%MOD)

Submission status: Accepted

Solution code:
MOD = 10**9+7
# dp[i][j] := Sの後ろからi桁を13で割った余りがjとなるようなものの個数
S = input()
l = len(S)
dp = [[0]*13 for _ in range(l+1)]
dp[0][0] = 1
mul = 1

for i in range(l):
    x = S[-(i+1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= MOD
    else:
        k = int(x) # これしか選ぶ余地なし
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= MOD
    mul = mul * 10 % 13
print(dp[len(S)][5])

Submission status: Accepted

Solution code:
MOD = 10**9+7
# dp[i][j] := Sの後ろからi桁を13で割った余りがjとなるようなものの個数
S = input()
dp = [[0]*13 for _ in range(len(S)+1)]
dp[0][0] = 1
mul = 1
l = len(S)
for i in range(l):
    x = S[-(i+1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= MOD
    else:
        k = int(x) # これしか選ぶ余地なし
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= MOD
    mul = mul * 10 % 13
print(dp[len(S)][5])

Submission status: Accepted

Solution code:
MOD = 10**9+7
# dp[i][j] := Sの後ろからi桁を13で割った余りがjとなるようなものの個数
S = input()
dp = [[0]*13 for _ in range(len(S)+1)]
dp[0][0] = 1
mul = 1
l = len(S)
for i in range(len(S)):
    x = S[-(i+1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= MOD
    else:
        k = int(x) # これしか選ぶ余地なし
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= MOD
    mul = mul * 10 % 13
print(dp[len(S)][5])

Submission status: Accepted

Solution code:
MOD = 10**9+7
# dp[i][j] := Sの後ろからi桁を13で割った余りがjとなるようなものの個数
S = input()
dp = [[0]*13 for _ in range(len(S)+1)]
dp[0][0] = 1
mul = 1  
for i in range(len(S)):
    x = S[-(i+1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= MOD
    else:
        k = int(x) # これしか選ぶ余地なし
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= MOD
    mul = mul * 10 % 13
print(dp[len(S)][5])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

mod = 10**9+7
s = readline().rstrip().decode('utf-8')

dp = [0]*13 #あまりが0~12の13通りとなる場合の数
dp[0] = 1
dig = 1 #今見てる桁数
for i in range(len(s)-1,-1,-1): #小さい方の桁から見ていく
    c = s[i]
    next_dp = [0]*13 #逐次更新してはいけないので、次の桁の数についてjを回して入れていく
    if c == "?": #?なら0~10の10通り全てについてあたる必要がある
        for d in range(10):
            for j in range(13):
                next_dp[(d*dig + j)%13] += dp[j]
                next_dp[(d*dig + j)%13] %= mod

    
    else:
        d = int(c)
        for j in range(13):
            next_dp[(d*dig + j)%13] += dp[j]
            next_dp[(d*dig + j)%13] %= mod


    dig *= 10
    dig %= 13
    dp = next_dp

print(dp[5]%mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
s = input()

A = []
for i in range(6):
    m = [-(j*10**i%13)%13 for j in range(10)]
    tmp = []
    for j in m:
        tmp.append([[1 if (k-l)%13==j else 0 for k in range(13)] for l in range(13)])
    tmp.append([[1 if (k-l)%13 in m else 0 for k in range(13)] for l in range(13)])
    A.append(tmp)
A = np.array(A)

dp = np.zeros(13, dtype=int)
dp[0] = 1
m = 1
for ind, i in enumerate(reversed(s)):
    i = int(i) if i!='?' else 10
    tmp = np.dot(A[ind%6, i, :, :], dp)
    dp = tmp%(10**9+7)
print(dp[5])

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 余りが0~12の桁DP
S = sr()
MOD = 10 ** 9 + 7
dp = [0] * 13 # 余り
dp[0] = 1
for s in S:
    prev = [x for x in dp]
    dp = [0] * 13
    if s == '?':
        add = range(10)
    else:
        add = [int(s)]
    for x in range(13):
        for a in add:
            dp[(10*x + a) % 13] += prev[x]
    dp = [y%MOD for y in dp]

print(dp[5])

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 余りが0~12の桁DP
S = sr()
MOD = 10 ** 9 + 7
dp = [[0] * 13 for _ in range(len(S)+1)]
dp[0][0] = 1
for i, s in enumerate(S):
    if s != '?':
        x = int(s)
        for j in range(13):
            dp[i+1][(10*j+x)%13] = dp[i][j]
    else:
        for j in range(13):
            for k in range(10):
                dp[i+1][(10*j+k)%13] += dp[i][j]
        for t in range(13):
            dp[i+1][t] %= MOD

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

Submission status: Accepted

Solution code:
import sys

def main():
    s = str(input())
    l = len(s)
    dp = [[0 for _ in range(13)] for _ in range(2)]
    MOD = 10**9+7
    dp[0][0] = 1
    now,use = 0,1
    
    for i in range(l):
        for j in range(13):
            if s[i] != "?":
                num = int(s[i])
                dp[use][(j*10+num)%13] += dp[now][j]
            else:
                for k in range(10):
                    dp[use][(j*10+k)%13] += dp[now][j]
        for j in range(13):
            dp[use][j] %= MOD
        dp[now] = [0 for _ in range(13)]
        now,use = use,now
    
    print(dp[now][5])

if __name__ == "__main__":
    main()

Submission status: Accepted

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

for i, s in enumerate(S[::-1], start=1):
    m = pow(10, i-1, 13)
    if s=="?":
        for k in range(13):
            for j in range(10):
                dp[i][(j*m+k)%13] += dp[i-1][k]
    else:
        j = int(s)
        for k in range(13):
            dp[i][(j*m+k)%13] += dp[i-1][k]
    
    for j in range(13):
        dp[i][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
mul = 1

MOD = 10**9 + 7

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

Submission status: Accepted

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

def main():
    s = str(input())
    l = len(s)
    ans = [0 for _ in range(13)]
    MOD = 10**9+7
    ans[0] = 1
    
    for st in s:
        dp = [0 for _ in range(13)]
        for i in range(13):
            dp[(10*i)%13] = ans[i]%MOD
        dp += dp
        if st != "?":
            for i in range(13):
                num = int(st)
                ans[i] = dp[i+13-num]
        else:
            for i in range(13):
                ans[i] = sum(dp[i+4:i+14])
    
    print(ans[5]%MOD)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from copy import deepcopy
# 多次元配列を作成する
def make_multi_list(initial, degree):
    ans = [initial for _ in range(degree[-1])]
    for d in reversed(degree[:-1]):
        ans = [deepcopy(ans) for _ in range(d)]
    return ans

S = input().strip()
N = len(S)
MOD = 10**9+7
dp = make_multi_list(0, [N+1, 13])
dp[0][0] = 1

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

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

Submission status: Accepted

Solution code:

# dp[i][k] := 先頭i桁を13で割った余りがkとなるものの個数 or
# dp[i][k] := 先頭i桁（残りはすべて0）を13で割った余りがkとなるものの個数
# どちらが良いか?
# 後者で。
# 先頭からでも下位からでもアルゴリズムは同じはず。下位からのほうが添え字が見やすい。
# →尺取っぽくやるのは下位の桁を追加したときだ。上位から決めないとダメじゃね?
# →前者じゃないとダメか。

# 配るDP
# 桁dがあれば：dp[i+1][k+ (d * 10 ** a)% 13] = dp[i][k]
# 桁が?ならば：10通りあるから10回配る? dp[i+1][k+ (d * 10 ** a)% 13] = dp[i][k]
# 10^5 * 10 * 13は無理じゃない?
# 全体-残り3つとして、+-しながら管理　（これができるのは1の桁の場合だけ）

s = input()
l = len(s)
dp = [[0 for _ in range(13)] for _ in range(l+1)]
dp[0][0] = 1
temp = [0] * 13
summ = 1
mod = 10 ** 9 + 7

for i in range(0, l):
    if s[i] != '?':
        for k in range(13):
            dp[i+1][(k*10+int(s[i])) % 13] = dp[i][k]
    else:
        # ?の場合
        for k in range(13):
            temp[(k*10) % 13] = dp[i][k]
        
        excluded = temp[1] + temp[2] + temp[3]
        for k in range(13):
            dp[i+1][k] = (summ - excluded) % mod
            excluded -= temp[(k+1)%13]
            excluded += temp[(k+4)%13]

        summ *= 10
        summ %= mod

print(dp[l][5])
# print(dp)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

ss = ins()
s = ss[::-1]
n = len(s)
a = [ [0]*13 for i in range(n) ]
r = 10
if s[0]=='?':
    for i in range(10):
        a[0][i] = 1
else:
    a[0][int(s[0])] = 1

for i in range(1,n):
    if s[i]=='?':
        ds = list(range(10))
    else:
        ds = [int(s[i])]
    for d in ds:
        for j in range(13):
            k = (j+d*r)%13
            #ddprint("r {} d {} j {} k {}".format(r,d,j,k))
            a[i][k] = (a[i][k]+a[i-1][j])%R
    r = (r*10)%13

if DBG:
    for i in range(6):
        printn(i)
        print(a[i])
print(a[n-1][5])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
S = list(input())[: -1]
K = 13
mod = 10 ** 9 + 7
dp = [[0] * (K) for _ in range(len(S) + 1)]
dp[0][0] = 1
for i in range(len(S)):
  for j in range(K):
    for k in range(10):
      if S[i] == "?":
        dp[i + 1][(j * 10 + k) % K] += dp[i][j]
        dp[i + 1][(j * 10 + k) % K] %= mod
      elif int(S[i]) == k:
        dp[i + 1][(j * 10 + k) % K] += dp[i][j]
        dp[i + 1][(j * 10 + k) % K] %= mod
print(dp[-1][5])

Submission status: Accepted

Solution code:
s = list(input())
n = len(s)
dp = [[0]*13 for i in range(n+1)]
dp[0][0] = 1
for i in range(n):
    flag = 1 if s[i]=='?' else 0
    for a in range(10):#i+1桁目の数字(0-9)
        if flag==1 or s[i]==str(a):
            for j in range(13): #あまり(0-12)
                dp[i+1][(j*10+a)%13] += dp[i][j] #i桁目の余りの10倍とi桁目を足して余りをだす
    for j in range(13):
        dp[i+1][j]%=10**9+7
print(dp[n][5])

Submission status: Accepted

Solution code:
s = list(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):
    flag = 1 if s[i]=='?' else 0 #?だったら1
    if flag==1:
        for a in range(10):#i+1桁目の数字(0-9)
            for j in range(13): #あまり(0-12)
                dp[i+1][(j*10+a)%13] += dp[i][j] #i桁目の余りの10倍とi桁目を足して余りをだす
    else:
        for j in range(13):
            a = int(s[i])
            dp[i+1][(j*10+a)%13] += dp[i][j]
    for j in range(13):
        dp[i+1][j]%=10**9+7
        
print(dp[n][5])

Submission status: Accepted

Solution code:
def main():
    S = input()
    N = len(S)
    MOD = 10 ** 9 + 7
    dp = [[0] * 13 for _ in range(N + 5)]
    dp[0][0] = 1

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

    print(dp[N][5])

    

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD=10**9+7

S=input()
N=len(S)
dp=[[0 for _ in range(13)] for _ in range(N)]
if S[0]=="?":
    for k in range(10):
        dp[0][k]=1
else:
    dp[0][int(S[0])]=1
for i in range(N-1):
    c=S[i+1]
    nums=[]
    if c=="?":
        nums=[i for i in range(10)]
    else:
        nums=[int(c)]
    for num in nums:
        for j in range(13):
            dp[i+1][(10*j+num)%13]+=dp[i][j]%MOD
print(dp[-1][5]%MOD)

Submission status: Accepted

Solution code:
S=input()
dp=[[0 for _ in range(13)] for _ in range(len(S))]
MOD=10**9+7
if S[0]=='?':
  for i in range(10):
    dp[0][i]=1
else:
  dp[0][int(S[0])]+=1
for i in range(1, len(S)):
  cur_nums=[i for i in range(10)] if S[i]=='?' else [int(S[i])]
  for cur in cur_nums:
    for rem in range(13):
      dp[i][(10*rem+cur)%13]=(dp[i][(10*rem+cur)%13]+dp[i-1][rem])%MOD
print(dp[-1][5])

Submission status: Accepted

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

# dp[i][j] := i桁目までで13で割ったあまりがjになるものの個数

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

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

print(dp[N][5])

Submission status: Accepted

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