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()
mod = 10**9+7

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

Submission status: Accepted

Solution code:
z=10
m=z**9+7
k=13
t=input()[::-1]
dp=[0]*k
dp[0]=1
for d in range(len(t)):
  p=[0]*k
  f=(t[d]=='?')
  for i in range(k):
    l=pow(z,d,k)
    for x in range(1+f*9):
      r=l*int(x if f else t[d])
      p[(i+r)%k]+=dp[i]
  dp=[j%m for j in p]
print(dp[5]%m)

Submission status: Accepted

Solution code:
S=input()
# S="".join(["?" for _ in range(10**5)])
# S = "??2??5"
# S= "?44"

MOD = 10**9+7
dp = [[0 for i in range(13)] for j in range(len(S)+1)]
dp[0][0] = 1
for t,ss in enumerate(S[::-1]):
    if t==0:
        tt = 1
    else:
        tt = (10*tt)%13
    if ss=="?":
        for i in range(13):
            for j in range(10):
                k = (j*tt+i)%13
                dp[t+1][k] += dp[t][i]%MOD
    else:
        s = int(ss)
        for i in range(13):
            k = (s*tt+i)%13
            dp[t+1][k] += dp[t][i]%MOD

print(dp[t+1][5]%MOD)

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

ans = dp[N][5]
print(ans)

Submission status: Accepted

Solution code:

S = input()

s = list(S)

s.reverse()

#print (s)

lis = [0] * 13
lis[0] = 1
keta = 1

for i in range(len(S)):

    nlis = [0] * 13



    for j in range(10):

        for k in range(13):

            if s[i]== "?" or j == int(s[i]):
                nlis[ (k + (j * keta)) % 13] += lis[k]

    keta *= 10
    keta = keta % 13
    for j in range(13):
        lis[j] = nlis[j] % (10**9 + 7)

#print (lis)
print (lis[5] % (10**9 + 7))

Submission status: Accepted

Solution code:
#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def main():
    mod = 10 ** 9 + 7
    s = list(input())
    n = len(s)
    s.reverse()

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

    mul = 1
    for i, c in enumerate(s):
        for j in range(10):
            if (c.isdigit() and int(c) == j) or c == '?':
                m = (j * mul) % 13
                for k in range(13):
                    dp[i + 1][(m + k) % 13] += dp[i][k]
        for k in range(13):
            dp[i + 1][k] = dp[i + 1][k] % mod
        mul *= 10
        mul %= 13
    print(dp[n][5])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

S = input()
M = 13
DP = [0] * M
DP[0] = 1

mul = 1
for i in range(len(S) - 1, -1, -1):
    s = S[i]
    newDP = [0] * M
    if s == '?':
        for k in range(10):
            for j in range(M):
                newDP[(mul * k + j) % M] += DP[j]
    else:
        k = int(s)
        for j in range(M):
            newDP[(mul * k + j) % M] += DP[j]
    DP = [x % MOD for x in newDP]
    mul *= 10
    mul %= M

print(DP[5])

Submission status: Accepted

Solution code:
import sys


fin = sys.stdin.readline
MOD = 10 ** 9 + 7
S = fin().rstrip("\n")[::-1]
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
base = 1
for i, c in enumerate(S, start=1):
    if c != '?':
        d = int(c) * base % 13
        for r in range(13):
            c = (d + r) % 13
            dp[i][c] += dp[i - 1][r]
            dp[i][c] %= MOD
    else:
        for d in range(10):
            d = d * base % 13
            for r in range(13):
                c = (d + r) % 13
                dp[i][c] += dp[i - 1][r]
                dp[i][c] %= MOD
    base = base * 10 % 13
print(dp[-1][5])

Submission status: Accepted

Solution code:
# import sys


# fin = sys.stdin.readline
MOD = 10 ** 9 + 7
S = input()[::-1]
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
base = 1
for i, c in enumerate(S, start=1):
    if c != '?':
        d = int(c) * base % 13
        for r in range(13):
            c = (d + r) % 13
            dp[i][c] += dp[i - 1][r]
            dp[i][c] %= MOD
    else:
        for d in range(10):
            d = d * base % 13
            for r in range(13):
                c = (d + r) % 13
                dp[i][c] += dp[i - 1][r]
                dp[i][c] %= MOD
    base = base * 10 % 13
print(dp[-1][5])

Submission status: Accepted

Solution code:
S = input().strip()

MOD = 10**9 + 7
dp = [[0 for i in range(13)] for j in range(100005)]
N = len(S)

dp[0][0] = 1
for i in range(N):
    c = -1
    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 = int(dp[N][5])

print(res)

Submission status: Accepted

Solution code:
# import sys


# fin = sys.stdin.readline
MOD = 10 ** 9 + 7
S = input()[::-1]
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
for i, c in enumerate(S, start=1):
    base = pow(10, i - 1, 13)
    if c != '?':
        d = int(c) * base % 13
        for r in range(13):
            c = (d + r) % 13
            dp[i][c] += dp[i - 1][r]
            dp[i][c] %= MOD
    else:
        for d in range(10):
            d = d * base % 13
            for r in range(13):
                c = (d + r) % 13
                dp[i][c] += dp[i - 1][r]
                dp[i][c] %= MOD
print(dp[-1][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-1][k]%=MOD
                dp[i][(k+j*m)%13]+=dp[i-1][k]
    else:
        for k in range(13):
            dp[i-1][k]%=MOD
            dp[i][(k+int(s[i])*m)%13]+=dp[i-1][k]
print(dp[-1][5]%(10**9+7))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
M = 10**9+7
S = input()
D = 13
# N = len(S)
dp = [0 for d in range(D)]
dp[0] = 1
mul = 1
for i in range(len(S)-1, -1, -1):
    nextDP = [0 for d in range(D)]
    c = S[i]
    if c == '?':
        for k in range(10):
            for j in range(D):
                nextDP[(k*mul+j)%D] += dp[j]
                nextDP[(k*mul+j)%D] %= M
    else:
        k = int(c)
        for j in range(D):
            nextDP[(k*mul+j)%D] += dp[j]
            nextDP[(k*mul+j)%D] %= M

    mul *= 10
    mul %= D
    dp = nextDP
print(dp[5])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    S = SI()
    N = len(S)
    S = reversed(S)
    dp = [[0 for j in range(13)] for i in range(N)]
 
    for i, es in enumerate(S):
        c = es
        if i == 0:
            if c == '?':
                for j in range(10):
                    dp[i][j] = 1
            else:
                dp[i][int(c)] = 1
        else:
            if c == '?':
                for j in range(10):
                    amari = (j * pow(10, i, 13)) % 13
                    for k in range(13):
                        dp[i][k] = (dp[i][k] + dp[i-1][(k-amari)%13]) % MOD
            else:
                amari = (int(c) * pow(10, i, 13)) % 13
                for k in range(13):
                    dp[i][k] += (dp[i][k] + dp[i - 1][(k-amari) % 13]) % MOD
 
    dprint(dp)
    print(dp[N-1][5])


solve()

Submission status: Accepted

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

S = str(input())
n = len(S)
if n==1:
  if S=='5' or S=='?':
    print(1)
  else:
    print(0)
  exit()

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
mod = 13

s = input()

num_digits = len(s)

dp = [[0 for _ in range(mod)] for _ in range(num_digits)]
if s[0] == '?':
    dp[0] = [1 for _ in range(10)] + [0 for _ in range(10, 13)]
else:
    dp[0][int(s[0])] = 1

for i, c in enumerate(s[1:]):
    if c == '?':
        targets = range(10)
    else:
        targets = [int(c)]

    for j in targets:
        for k in range(mod):
            dp[i + 1][(k * 10 + j) % mod] += dp[i][k]

    for k in range(mod):
        dp[i + 1][k] %= int(10**9 + 7)

print(dp[-1][5])

Submission status: Accepted

Solution code:
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
for i in range(1,l):
    mod = pow(10,i,13)
    if s[i] == "?":
        for j in range(10):
            for k in range(13):
                dp[i-1][k] %= 10**9+7
                dp[i][(k+j*mod)%13] += dp[i-1][k]
    else:
        for k in range(13):
            dp[i-1][k] %= 10**9+7
            dp[i][(k+int(s[i])*mod)%13] += dp[i-1][k]
print(dp[-1][5]%(10**9+7))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    S = SI()
    S = S[::-1]
    N = len(S)
    dp = [0 for j in range(13)]
    dp2 = [0 for j in range(13)]

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

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

    dprint(dp)
    print(dp[5])



solve()

Submission status: Accepted

Solution code:
import math
 
s = list(map(str, input().split()))
s = s[0]
n = len(s)

now = 1
amari = []
for i in range(len(s)):
    amari.append(now)
    now = (now * 10) % 13

ans = [[0 for i in range(13)] for j in range(2)]
ans[0][0] = 1
ans[1][0] = 1

for i in range(len(s)):
    now = s[n-1-i]
    ans[(i+1)%2] = [0 for i in range(13)]
    if(now=="?"):
        for k in range(10):
            plus = (amari[i] * k)%13
            for j in range(13):
                ans[(i+1)%2][(j+plus)%13] += ans[i%2][j]
                ans[(i+1)%2][(j+plus)%13] %= 1000000007
    else:
        now = int(now)
        plus = (amari[i] * now)%13
        for j in range(13):
            ans[(i+1)%2][(j+plus)%13] = ans[i%2][j]
            
    last = (i+1)%2
            
print(ans[last][5])

Submission status: Accepted

Solution code:
S = input()
N = len(S)

mod = 10**9 +7
dp = [[0] * 13 for i in range(10**6)]

dp[0][0] = 1
for i,s in enumerate(S):
    keta = (N-i-1)%6
    if s != "?":
        for j in range(13):
            amari = (j + int(s)*10**keta)%13 #桁を追加
            dp[i+1][amari] += dp[i][j]
    else:
        for j in range(13):
            for k in range(10):
                amari = (j + k*10**keta)%13
                dp[i+1][amari] += dp[i][j]
    for j in range(13):
        dp[i+1][j] %= mod
print(dp[N][5]%mod)

Submission status: Accepted

Solution code:
S=input()
N=len(S)
X=[1,10,9,12,3,4]
Y=[0,0,0,0,0,0]
nowmod=0
modprime=10**9+7
for i in range(N):
    if S[-i-1]=="?":
        Y[i%6]+=1
    else:
        nowmod+=X[i%6]*int(S[-i-1])
        nowmod%=13
#print(nowmod,Y)
#?は0~9まで選べる
M=max(Y)
dp=[[0 for j in range(13)]for i in range(M+1)]
#dp[i][j]:全部でi個あるグループの総和がmod 13でjになるパターン数(mod 10**9+7)
dp[0][0]=1
for i in range(M):
    for k in range(10):
        for j in range(13):
            dp[i+1][(k+j)%13]+=dp[i][j]
            dp[i+1][(k+j)%13]%=modprime
table=[[dp[Y[i]][j] for j in range(13)]for i in range(6)]
ans=[[0 for j in range(13)] for i in range(7)]
ans[0][0]=1
for i in range(6):
    for j in range(13):
        for k in range(13):
            ans[i+1][(j+(X[i]*k))%13]+=ans[i][j]*table[i][k]
            ans[i+1][(j+(X[i]*k))%13]%=modprime
print(ans[6][(5-nowmod)%13])

Submission status: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

S = input()
n = len(S)
dp = [[0]*(13) for _ in range(n+1)]
dp[0][0]=1
for i in range(n):
    c = 0
    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

print(dp[n][5])

Submission status: Accepted

Solution code:
s = list(input())

digits = len(s)
s.reverse()
dp = [ [0] * 13 for i in range(digits)]
# dp[i][j] は i+1桁目までで13で割った余りがjのものを格納する
mod = 10 ** 9 + 7
power = 1

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

Submission status: Accepted

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10

MOD = 10 ** 9 + 7

# 1 <= |S| <= 10^5
S = [c for c in stdin.readline().rstrip()]
N = len(S)


# dp[i][j] := 先頭i文字として考えられるもののうち，13で割ったあまりがjであるものの数
# dp[100005][13]
dp = [[0] * 13 for _ in range(10**5+5)]

dp[0][0] = 1

for i in range(N):
    c = 0
    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


ans = dp[N][5]

print(ans)

Submission status: Accepted

Solution code:
def main():
    s = input().strip()

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

    power = 1
    mod = 10 ** 9 + 7
    for c in reversed(s):
        ndp = [0] * 13
        for rem in range(13):
            candidate = range(10) if c == '?' else [int(c)]
            for digit in candidate:
                nrem = (rem + digit * power) % 13
                ndp[nrem] = (ndp[nrem] + dp[rem]) % mod
        dp = ndp
        power = (power * 10) % 13
    print(dp[5])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

mod = 10 ** 9 + 7
S = input()[::-1]
W = [1, 10, 9, 12, 3, 4]

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

for i, s in enumerate(S):
    if i == 0:
        if s == "?":
            for j in range(10):
                dp[0][j] = 1
        else:
            dp[0][int(s)] = 1
        continue

    w = W[i % 6]
    if s == "?":
        for n in range(10):
            r = (n * w) % 13
            for j in range(13):
                dp[i][(j + r) % 13] = (dp[i][(j + r) % 13] + dp[i - 1][j]) % mod

    else:
        n = int(s)
        r = (n * w) % 13
        for j in range(13):
            dp[i][(j + r) % 13] = (dp[i][(j + r) % 13] + dp[i - 1][j]) % mod

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

Submission status: Accepted

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

MOD = pow(10, 9) + 7

def main():
  s = input().strip()
  sd = [[0 for _ in range(13)] for _ in range(len(s))]
  if s[-1] == '?':
    for i in range(10):
      sd[0][i] = 1
  else:
    sd[0][int(s[-1])] = 1

  for i, _s in enumerate(s[::-1]):
    if i == 0:
      continue
    if _s != '?':
      rem = int(_s) * pow(10, i, 13) % 13
      for j in range(13):
        sd[i][(j+rem)%13] = sd[i-1][j]
    else:
      for k in range(10):
        rem = k * pow(10, i, 13) % 13
        for j in range(13):
          sd[i][(j+rem)%13] += sd[i-1][j]
          sd[i][(j+rem)%13] %= MOD
  print(sd[len(s)-1][5])


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
divisor = 1000000007
# 文字列を一文字ずつのリストに代入 test は['t', 'e', 's', 't']
s = list(input())
t = []

for i in range( len(s) ):
    if s[i] == '?':
        t.append(-1)
    else:
        t.append(int(s[i]))

dp = [[0 for i in range(13)] for i in range(100005)]
dp[0][0]=1
for i in range(len(s)):
    for j in range(10):
        if t[i] == -1 or t[i] == j:
            for k in range(13):
                dp[i+1][(k*10+j)%13] += dp[i][k]
    for j in range(13):
        dp[i+1][j] = dp[i+1][j] % divisor

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

Submission status: Accepted

Solution code:
S = input()

MOD = 10 ** 9 + 7
MAX_LEN = len(S)
dp = [[0] * 13 for _ in range(MAX_LEN + 1)]
dp[0][0] = 1

for i in range(MAX_LEN):
    c = int(S[i]) if S[i] != '?' else -1
    for j in range(10):
        if c != -1 and c != j:
            continue
        
        for k in range(13):
            idx = (k * 10 + j) % 13
            dp[i + 1][idx] += dp[i][k]
            dp[i + 1][idx] %= MOD
        
print(dp[-1][5])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
from numpy.fft import fft, ifft

mod = 10 ** 9 + 7
S = input()

mat = []
for i in range(6):
    w = np.zeros(13)
    for j in range(10):
        w[(10 ** i * j) % 13] += 1
    mat.append(fft(w))

ress = [[(10 ** i * j) % 13 for j in range(10)] for i in range(6)]


state = np.zeros(13)
state[0] = 1
state = fft(state)

keta = 0
res = 5
for s in reversed(S):
    if s == "?":
        state = state * mat[keta]
    else:
        res -= ress[keta][int(s)]

    if keta == 5:
        keta = 0
        state = fft(np.remainder(np.round(np.real(ifft(state))), mod))
    else:
        keta += 1


state = ifft(state)
print(int(np.round(np.real(state[res % 13]))) % mod)

Submission status: Accepted

Solution code:


s = input()
buf = [0 for i in range(13)]
s = s[::-1]
n = len(s)
# print(s)

base = 10

if s[0] == "?":
    buf = [1,1,1,1,1,1,1,1,1,1,0,0,0]
else:
    buf[int(s[0])] = 1
# print(buf)
# print("############")
for i in range(1,n):
    base = base%13
    nbuf = [0 for j in range(13)]
    if s[i] == "?":
        ooo = [0 for j in range(13)]
        for j in range(10):
            temp = (base*j)%13
            ooo[temp] += 1
        # print(ooo)
        for j in range(13):
            for k in range(13):
                temp = (j+k)%13
                nbuf[temp]+= buf[k]*ooo[j]
                nbuf[temp] %= (10**9+7)
    else:
        for j in range(13):
            temp = j+int(s[i])*base
            temp %= 13
            nbuf[temp] += buf[j]
            nbuf[temp] %= (10 ** 9 + 7)
    base *= 10
    buf = nbuf
    # print(buf)
    # print("*********************")

# print(buf)
print(buf[5])

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
mod = 10**9+7
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))

n = list(input())
n.reverse()
nnn = len(n)
di = 1
dp = [0 for i in range(13)]
d = [0 for i in range(13)]

if n[0] == '?':
	for i in range(10):
		d[i] = 1
else:
	d[int(n[0])] = 1

for i in range(1,nnn):
	dp = [0 for i in range(13)]
	di *= 10
	di %= 13
	if n[i] == "?":
		for j in range(10):
			j = j * di
			j %= 13
			for kk in range(13):
				dp[(j + kk)%13] += d[kk]
				dp[(j + kk)%13] %= mod
	else:
		k = int(n[i])
		k = k * di
		k %= 13
		for kk in range(13):
			dp[(k + kk)%13] += d[kk]
			dp[(k + kk)%13] %= mod
	d = dp[:]
print(d[5]%mod)

Submission status: Accepted

Solution code:
S = input()
N = len(S)
DP =[0]*13
DP[0] = 1
A = 0
MOD = 10**9+7

T = [1,10,9,12,3,4]
A = 0
for i in range(N):
    A*=10
    if S[i] == "?":
        hoge = [0]*13
        for j in range(13):
            for k in range(10):
                hoge[(j+k*T[(N-i-1)%6])%13] = (hoge[(j+k*T[(N-i-1)%6])%13] + DP[j])%MOD
        DP = hoge[:]
    else:
        A += int(S[i])
    A = A%13
print(DP[(5-A)%13])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
MOD = 10**9+7

S = input()[:-1]
#dp[文字列をしたの桁からI番目まで見て][あまりがjになる数] = のこすう
dp = [[0]*13 for _ in range(len(S)+1)]
dp[0][0] = 1

# 文字列を逆順から見ていく
S = list(reversed(S))
for i in range(len(S)):
    if S[i] == "?":
        dig = pow(10, i, 13)
        # ?だと新しく追加する数を10通り試す
        for k in range(10):  # 新しく追加する数
            for j in range(13):  # 各あまりからの遷移
                dp[i+1][(k*dig+j) % 13] += dp[i][j]
                dp[i+1][(k*dig+j) % 13] %= MOD
    else:
        dig = pow(10, i, 13)
        #dig = 10**i
        for j in range(13):
            dp[i+1][(int(S[i])*dig+j) % 13] += dp[i][j]
            dp[i+1][(int(S[i])*dig+j) % 13] %= MOD

print(dp[-1][5])

Submission status: Accepted

Solution code:
def main():
    mod=1000000007
    s=input()
    l=len(s)
    DP=[[0]*13 for _ in range(l+1)]
    DP[0][0]=1
    for i in range(1,l+1):
        d=s[-i]
        tmp=pow(10,i-1,13)
        if d=='?':
            for j in range(10):
                for k in range(13):
                    m=(k+tmp*j)%13
                    DP[i][m]+=DP[i-1][k]
                    if DP[i][m]>=mod:
                        DP[i][m]-=mod
        else:
            d=int(d)
            for k in range(13):
                m=(k+tmp*d)%13
                DP[i][m]+=DP[i-1][k]
                if DP[i][m]>=mod:
                    DP[i][m]-=mod
    print(DP[-1][5])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
MOD = 10**9+7


def brute():
    S = input()[:-1]
    print(S)

    Q = [""]
    for c in reversed(S):
        tmp = []
        if c == "?":
            print("?")
            for q in Q:
                for i in range(0, 10):
                    tmp.append(str(i)+q)
        else:
            for q in Q:
                tmp.append(c+q)
        Q = tmp

    Q = sorted(Q)
    cnt = 0
    for q in Q:
        if int(q) % 13 == 5:
            cnt += 1
            print(int(q))
    print(cnt)
    print(cnt % MOD)


def solve():
    S = input()[:-1]
    # dp[i+1][j]イバン目まで見て、あまりがjのこすう
    dp = [[0]*13 for _ in range(len(S)+1)]
    dp[0][0] = 1

    S = list(reversed(S))
    for i in range(len(S)):
        if S[i] == "?":
            #dig = 10**i
            dig = pow(10, i, 13)
            for k in range(10):
                for j in range(13):
                   # dp[i+1][j] += dp[i][(k*dig+j) % 13]
                    dp[i+1][(k*dig+j) % 13] += dp[i][j]
                    dp[i+1][(k*dig+j) % 13] %= MOD

            pass
        else:
            dig = pow(10, i, 13)
            #dig = 10**i
            for j in range(13):
                dp[i+1][(int(S[i])*dig+j) % 13] += dp[i][j]
                #dp[i+1][j] = dp[i][(int(S[i])*dig+j) % 13]
                dp[i+1][(int(S[i])*dig+j) % 13] %= MOD

    ans = dp[-1][5]
    print(ans)


solve()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
S = input()
if S[-1] == '?':
  dp = [1,1,1,1,1,1,1,1,1,1,0,0,0]
  dpsum = 10
else:
  dp = [0] * 13
  dp[int(S[-1])] = 1
  dpsum = 1

unitmod = 1
for i, c in enumerate(list(reversed(S))[1:]):
  ndp = [0] * 13
  ndpsum = 0
  unitmod = unitmod * 10 % 13
  if c == '?':
    s = set([1,2,3,4,5,6,7,8,9,10,11,12])
    tm = unitmod
    for _ in range(9):
      s.discard(tm)
      tm = (tm + unitmod) % 13
    for j in range(13):
      x = dpsum
      for e in s:
        x -= dp[(j-e) % 13]
        x %= MOD
      ndp[j] = x
      ndpsum += x
  else:
    mod = unitmod * int(c) % 13
    for j in range(13):
      x = dp[(j-mod) % 13]
      x %= MOD
      ndp[j] = x
      ndpsum += x
  dp = ndp
  dpsum = ndpsum % MOD
print(dp[5])

Submission status: Accepted

Solution code:
z=10
m=z**9+7
k=13
t=input()[::-1]
dp=[0]*k
dp[0]=1
for d in range(len(t)):
  p=[0]*k
  if t[d]=='?':
    for x in range(z):
      r=int(x)*pow(z,d,k)
      for i in range(k):
        p[(i+r)%k]+=dp[i]
  else:
    r=int(t[d])*pow(z,d,k)
    for i in range(k):
      p[(i+r)%k]+=dp[i]
  dp=[j%m for j in p]
print(dp[5]%m)

Submission status: Accepted

Solution code:
info = [[[[0] * 13 for i in range(11)] for j in range(11)] for k in range(11)]
memo = [0 for i in range(13)]
memo2 = [0 for i in range(13)]
memo2[0] = 1
memo3 = [0 for i in range(13)]
memo3[0] = 1

s = input()
if len(s) % 3 > 0:
  s = "0" * (3 - len(s) % 3) + s

for i in range(10):
  for j in range(10):
    for k in range(10):
      info[i][j][k][(i * 100 + j * 10 + k) % 13] = 1

for i in range(10):
  for j in range(10):
    for k in range(10):
      for l in range(13):
        info[10][j][k][l] += info[i][j][k][l]

for i in range(11):
  for j in range(10):
    for k in range(10):
      for l in range(13):
        info[i][10][k][l] += info[i][j][k][l]

for i in range(11):
  for j in range(11):
    for k in range(10):
      for l in range(13):
        info[i][j][10][l] += info[i][j][k][l]

v = [s[i: i+3] for i in range(0, len(s), 3)]
v.reverse()

for i in range(len(v)):
  for j in range(13):
    memo[j] = info[10 if v[i][0] == "?" else int(v[i][0])][10 if v[i][1] == "?" else int(v[i][1])][10 if v[i][2] == "?" else int(v[i][2])][j]
    memo2[j] = 0
  for j in range(13):
    for k in range(13):
      if i % 2 == 1:
        memo2[(j - k) % 13] += memo3[j] * memo[k]
      else:
        memo2[(j + k) % 13] += memo3[j] * memo[k]
  for j in range(13):
    memo2[j] = memo3[j] = (memo2[j]) % (10 ** 9 + 7)

print(memo2[5])