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:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

s = sys.stdin.readline()
n = len(s)-1
now = [0] * 13
now[0] = 1
for i in range(n)[::-1]:
    prev = now[::]
    now = [0] * 13
    c = n - i - 1#桁
    m = pow(10,c,13)
    if s[i] == '?':
        for k in range(10):
            l = (m*k) % 13
            for j in range(13):
                now[(j+l)%13] += prev[j]
                now[(j+l)%13] = now[(j+l)%13] % mod
    else:
        k = int(s[i])
        l = (m*k) % 13
        for j in range(13):
            now[(j+l)%13] = prev[j]
    # print(now)
print(now[5])

Submission status: Accepted

Solution code:
n=input()
l1=list(n)
l1=l1[::-1]
num=len(n)
ans=[0 for i in range(13)]
modlist=[1,10,9,12,3,4]
if l1[0]=="?":
  for i in range(0,10):
    ans[i]=1
else:
  ans[int(l1[0])]=1
for i in range(1,num):
  mod=modlist[i%6]
  dp=[ans[i] for i in range(13)]
  if l1[i]=="?":
    lmod=[(j*mod)%13 for j in range(10)]
    for j in range(13):
      ans1=0
      for k in lmod:
        if j-k>=0:
          mod2=j-k
        else:
          mod2=13+j-k
        ans1=(ans1+dp[mod2])%(10**9+7)
      ans[j]=ans1%(10**9+7)
  else:
    num1=int(l1[i])
    mod1=(num1*mod)%13
    for j in range(13):
      if j-mod1>=0:
        mod2=j-mod1
      else:
        mod2=13+j-mod1
      ans[j]=dp[mod2]
print(ans[5]%(10**9+7))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



s = S()
d = len(s)
dp = [[0] * 13 for _ in range(d + 1)]
dp[0][0] = 1
for i in range(d):
    for j in range(13):
        if s[i] != '?':
            dp[i + 1][(j * 10 + int(s[i])) % 13] = (dp[i + 1][(j * 10 + int(s[i])) % 13] + dp[i][j]) % mod
        else:
            for k in range(10):
                dp[i + 1][(j * 10 + k) % 13] = (dp[i + 1][(j * 10 + k) % 13] + dp[i][j]) % mod


print(dp[d][5])

Submission status: Accepted

Solution code:
S = input()
 
MOD = 10 ** 9 + 7
N = 13
 
DP = [0] * N
 
# 初期値
DP[0] = 1
digit = 1
 
# 0 -> 5 -> ?5 -> ??5 -> ...に対する余りがどこになるかを更新していく
for i in range(len(S) - 1, -1, -1):
    nextDP = [0] * N
 
    if S[i] == "?":
        for k in range(10):
            for j in range(N):
                nextDP[(k * digit + j) % N] += DP[j]
                nextDP[(k * digit + j) % N] %= MOD
    else:
        k = int(S[i])
        for j in range(N):
            nextDP[(k * digit + j) % N] += DP[j]
            nextDP[(k * digit + j) % N] %= MOD
 
    digit *= 10
    digit %= N
    DP = nextDP[:]
 
print(DP[5])
 
"""
??2??5

"""

Submission status: Accepted

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

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=read().rstrip().decode("utf-8")
#print("S:",S)

R=[0]*13
R_buffer=[0]*13

if S[0]=="?":
  for i in range(0,10):
    R[i]=1
else:
  R[int(S[0])]=1
#print("R:",R)

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

Submission status: Accepted

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


def main():
    S = input().strip()
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] = 1
    m = 1
    for n in range(N):
        c = S[N-n-1]
        for i in range(10):
            if c == "?" or int(c) == i:
                for j in range(13):
                    dp[n+1][(j + i*m)%13] += dp[n][j]
        for i in range(13):
            dp[n+1][i] %= 10**9+7
        m = m * 10 % 13
    print(dp[N][5])


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main():
    S = input().strip()
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] = 1
    m = 1
    for n in range(N):
        c = S[N-n-1]
        if c == "?":
            for i in range(10):
                for j in range(13):
                    dp[n+1][(j + i*m)%13] += dp[n][j]
        else:
            k = int(c)
            for j in range(13):
                dp[n+1][(j + k*m)%13] += dp[n][j]
        for i in range(13):
            dp[n+1][i] %= 10**9+7
        m = m * 10 % 13
    print(dp[N][5])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

sl = list(input())

dp = [[0 for i in range(13)] for i in range(len(sl)+1)]
dp[0][0] = 1
for idx, s in enumerate(sl):
    if s == "?":
        n = -1
    else:
        n = int(s)
    for j in range(13):
        for i in range(10):
            if n == -1 or n == i: 
                dp[idx+1][(10*j+i) % 13] += dp[idx][j]
                dp[idx+1][(10*j+i) % 13] %= 10**9 + 7

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

Submission status: Accepted

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

Submission status: Accepted

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

s = ''.join(list(reversed(s)))

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
s=list(input())
mod=10**9+7
for i in range(len(s)):
    if s[i]=='?':
        s[i]=-1
    else:
        s[i]=int(s[i])

dp=[[0]*13 for i in range(len(s)+1)]
s.reverse()
dp[0][0]=1
y=[]
x=1
for i in range(len(s)):
    if s[i]!=-1:
        z=s[i]*x

        for j in range(13):
            dp[i+1][(j+z)%13]+=dp[i][j]%mod
    else:
        for j in range(10):
            y.append((x*j)%mod)

        for k in range(13):
            for l in range(len(y)):
                dp[i+1][(k+y[l])%13]+=dp[i][k]%mod
        y=[]
    x=(x*10)%13
        
print(dp[len(s)][5]%mod)

Submission status: Accepted

Solution code:
s=list(input())
mod=10**9+7
for i in range(len(s)):
    if s[i]=='?':
        s[i]=-1
    else:
        s[i]=int(s[i])

dp=[[0]*13 for i in range(len(s)+1)]
s.reverse()
dp[0][0]=1
y=[]
x=1
for i in range(len(s)):
    if s[i]!=-1:
        z=s[i]*x

        for j in range(13):
            dp[i+1][(j+z)%13]+=dp[i][j]%mod
    else:
        for j in range(10):
            y.append(x*j)

        for k in range(13):
            for l in range(len(y)):
                dp[i+1][(k+y[l])%13]+=dp[i][k]%mod
        y=[]
    x=(x*10)%13
        
print(dp[len(s)][5]%mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
S = list(input())[: -1]
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):
    for k in range(10):
      if S[i] == "?":
        dp[i + 1][(j * 10 + k) % 13] += dp[i][j]
        dp[i + 1][(j * 10 + k) % 13] %= mod
    if S[i] != "?":
      dp[i + 1][(j * 10 + int(S[i])) % 13] += dp[i][j]
      dp[i + 1][(j * 10 + int(S[i])) % 13] %= mod
print(dp[-1][5])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    M=13
    S=input()
    n=len(S)
    dp=[0]*M
    dp[0]=1
    for i in range(n):
        ndp=[0]*M
        s=S[i]
        if(s=='?'):
            for j in range(10):
                for m in range(M):
                    ndp[(m*10+j)%M]+=dp[m]
                    ndp[(m*10+j)%M]%=MOD
        else:
            s=int(s)
            for m in range(M):
                ndp[(m*10+s)%M]+=dp[m]
        dp=ndp
    print(dp[5])
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    M=13
    S=input()[::-1]
    n=len(S)
    dp=[0]*M
    dp[0]=1
    for i in range(n):
        ndp=[0]*M
        s=S[i]
        d=pow(10,i,M) # d=10^i mod 13
        if(s=='?'):
            for j in range(10):
                for m in range(M):
                    ndp[(m+j*d)%M]+=dp[m]
                    ndp[(m+j*d)%M]%=MOD
        else:
            s=int(s)
            for m in range(M):
                ndp[(m+s*d)%M]+=dp[m]
        dp=ndp
    print(dp[5])
resolve()

Submission status: Accepted

Solution code:
import copy
s = str(input())
N = len(s)
num = [0,0,0,0,0,0]
all = [76923 for i in range(13)]
all[0] = 76924

num1 = [1,1,1,1,1,1,1,1,1,1,0,0,0] # 10**(6k)
num2 = [1,1,1,0,1,1,0,1,1,0,1,1,1] # 10**(6k+1)
num3 = [1,1,1,1,0,1,1,1,0,1,1,1,0] # 10**(6k+2)
num4 = [1,0,0,0,1,1,1,1,1,1,1,1,1] # 10**(6k+3)
num5 = [1,1,1,1,0,1,1,0,1,1,0,1,1] # 10**(6k+4)
num6 = [1,0,1,1,1,0,1,1,1,0,1,1,1] # 10**(6k+5)

tgt = copy.deepcopy(all)

md = 0
for i in range(N):
    t = s[N-i-1]
    if t == '?':
        num[i%6] += 1
    else:
        md += ((10**(i%6)) * int(t))%13
allnum = min(num)
for i in range(6):
    num[i] -= allnum
#print(num)

if allnum == 0:
    tgt = [0,0,0,0,0,0,0,0,0,0,0,0,0]
    tgt[md%13] = 1
else:
    for i in range(allnum-1):
        tgt2 = [0,0,0,0,0,0,0,0,0,0,0,0,0]
        for j in range(13):
            for k in range(13):
                tgt2[(j+k)%13] += all[j]*tgt[k]
        for j in range(13):
            tgt2[j] = tgt2[j]%(10**9+7)
        tgt = copy.deepcopy(tgt2)

for i in range(num[0]):
    tgt2 = [0,0,0,0,0,0,0,0,0,0,0,0,0]
    for j in range(13):
        for k in range(13):
            tgt2[(j+k)%13] += tgt[j]*num1[k]
    for j in range(13):
        tgt2[j] = tgt2[j]%(10**9+7)
    tgt = copy.deepcopy(tgt2)
for i in range(num[1]):
    tgt2 = [0,0,0,0,0,0,0,0,0,0,0,0,0]
    for j in range(13):
        for k in range(13):
            tgt2[(j+k)%13] += tgt[j]*num2[k]
    for j in range(13):
        tgt2[j] = tgt2[j]%(10**9+7)
    tgt = copy.deepcopy(tgt2)
for i in range(num[2]):
    tgt2 = [0,0,0,0,0,0,0,0,0,0,0,0,0]
    for j in range(13):
        for k in range(13):
            tgt2[(j+k)%13] += tgt[j]*num3[k]
    for j in range(13):
        tgt2[j] = tgt2[j]%(10**9+7)
    tgt = copy.deepcopy(tgt2)
for i in range(num[3]):
    tgt2 = [0,0,0,0,0,0,0,0,0,0,0,0,0]
    for j in range(13):
        for k in range(13):
            tgt2[(j+k)%13] += tgt[j]*num4[k]
    for j in range(13):
        tgt2[j] = tgt2[j]%(10**9+7)
    tgt = copy.deepcopy(tgt2)
for i in range(num[4]):
    tgt2 = [0,0,0,0,0,0,0,0,0,0,0,0,0]
    for j in range(13):
        for k in range(13):
            tgt2[(j+k)%13] += tgt[j]*num5[k]
    for j in range(13):
        tgt2[j] = tgt2[j]%(10**9+7)
    tgt = copy.deepcopy(tgt2)
for i in range(num[5]):
    tgt2 = [0,0,0,0,0,0,0,0,0,0,0,0,0]
    for j in range(13):
        for k in range(13):
            tgt2[(j+k)%13] += tgt[j]*num6[k]
    for j in range(13):
        tgt2[j] = tgt2[j]%(10**9+7)
    tgt = copy.deepcopy(tgt2)
#print(tgt)
if allnum == 0:
    print(tgt[5])
else:
    print(tgt[(5-md)%13])

Submission status: Accepted

Solution code:
# ABC135D - Digits Parade
# digit DP
def main():
    S = input().rstrip()
    ans, MOD = [0] * 13, 10 ** 9 + 7
    ans[0] = 1
    for c in S:
        dp = [0] * 13
        for i in range(13):
            dp[(i * 10) % 13] = ans[i] % MOD
        dp += dp
        if c == "?":
            for i in range(13):
                ans[i] = sum(dp[i + 4 : i + 14])
        else:
            x = int(c)
            for i in range(13):
                ans[i] = dp[i + 13 - x]
    print(ans[5] % MOD)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)
S = str(input())
N = len(S)
M = 13
#c = [0]*(N)
#for i in range(N):
#    c[i] = (10**i)%M
#    c[i] = pow(10,i,M)
#print(c)
#c.reverse()
#print(c)
"""
dp = [[0]*M for _ in range(N+1)]
i = int(0)
for j in range(M):
    dp[0][j] = 1
for s in S:
    if s == "?":
        for l in range(10):
            m = l * c[i] % M
            dp[i+1][(M - m) % M] += dp[i][j]
    else:
        m = int(s) * c[i] % M
        dp[i][(M - m) % M] +=dp[i][j]
    i +=1




dp = [[0]*M for _ in range(N)]
c = (10**(N-1))%M
if S[0] == "?":
    for l in range(10):
        dp[0][l*c%M] += 1
else:
    m = int(S[0]) * c%M
    dp[0][m] = 1
S = S[1:]
i = int(1)
for s in S:
    c = (10 ** (N - 1-i)) % M
    if s == "?":
        for j in range(13):
            for l in range(10):
                dp[i][j] += dp[i-1][(j-l*c)%13]
    else:
        st = int(s)
        for j in range(13):
            dp[i][j] = dp[i-1][(j-st*c)%13]
    i +=1


dp = [[0]*M for _ in range(N)]
if S[0] == "?":
    for l in range(10):
        m = l * c[0]%M
        dp[0][m] += 1
else:
    m = int(S[0]) * c[0]%M
    dp[0][m] = 1

for i in range(1,N):
    if S[i] == "?":
        for j in range(M):
            for l in range(10):
                m = l*c[i]%M
                dp[i][j] += dp[i-1][(M+j-m)%M]
    else:
        for j in range(M):
            m = int(S[i])*c[i]%M
            dp[i][j] = dp[i-1][(M+j-m)%M]

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

dp = [[0]*M for _ in range(N)]
for i in range(N):
    if i == 0:
        if S[-i - 1] == "?":
            for j in range(10):
                dp[i][j] += 1
        else:
            dp[i][int(S[-i - 1])] += 1
    else:
        mult = pow(10, i, 13)
        if S[-i - 1] == "?":
            for j in range(13):
                for k in range(10):
                    dp[i][(k * mult + j) % 13] += dp[i - 1][j]
        else:
            st = int(S[-i - 1])
            for j in range(13):
                dp[i][(st * mult + j) % 13] += dp[i - 1][j]
    for j in range(13):
        dp[i][j] = dp[i][j] % mod

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

Submission status: Accepted

Solution code:
import sys
 
 
def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    s = str(input().rstrip('\n'))
    ls = [[0] * 13 for _ in range(len(s))]
    for i in range(len(s)):
        if i == 0:
            if s[-i-1] == "?":
                for j in range(10):
                    ls[i][j] += 1
            else:
                ls[i][int(s[-i-1])] += 1
        else:
            mult = pow(10, i, 13)
            if s[-i-1] == "?":
                for j in range(13):
                    for k in range(10):
                        ls[i][(k * mult + j) % 13] += ls[i-1][j]
            else:
                st = int(s[-i-1])
                for j in range(13):
                    ls[i][(st * mult + j) % 13] += ls[i-1][j]
        for j in range(13):
            ls[i][j] = ls[i][j] % mod
    print(ls[-1][5])
 
 
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
S = input()
dp = [[0 for _ in range(13)] for _ in range(2)]
dp[0][0] = 1
bit = 0
for c in S:
    if c == '?':
        for k in range(13):
            for s in range(10):
                dp[bit^1][(10*k+s) % 13] += dp[bit][k]
    else:
        for k in range(13):
            dp[bit^1][(10*k+int(c)) % 13] += dp[bit][k]
    
    for k in range(13):
        dp[bit^1][k] %= (10 ** 9 + 7)
        dp[bit][k] = 0
    bit ^= 1
print(dp[bit][5])

Submission status: Accepted

Solution code:
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    s = str(input().rstrip('\n'))
    ls = [[0] * 13 for _ in range(len(s))]
    for i in range(len(s)):
        if i == 0:
            if s[-i-1] == "?":
                for j in range(10):
                    ls[i][j] += 1
            else:
                ls[i][int(s[-i-1])] += 1
        else:
            mult = pow(10, i, 13)
            if s[-i-1] == "?":
                for j in range(13):
                    for k in range(10):
                        ls[i][(k * mult + j) % 13] += ls[i-1][j]
            else:
                st = int(s[-i-1])
                for j in range(13):
                    ls[i][(st * mult + j) % 13] += ls[i-1][j]
        for j in range(13):
            ls[i][j] = ls[i][j] % mod
    print(ls[-1][5])


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
  S = str(input())
 
  ans = [0] * 13
  ans[0] = 1
  MOD = 10**9 + 7

  for i in S:
      dp = [0] * 13
      for j in range(13):
          dp[(j * 10) % 13] = ans[j] % MOD
      dp += dp
      if i == '?':
          for j in range(13):
              ans[j] = sum(dp[j+4:j+14])
      else:
          for j in range(13):
              ans[j] = dp[j + 13 - int(i)]

  print(ans[5] % MOD)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    S = [int(i) if i != '?' else -1 for i in input()]
    s = len(S)
    mod = 10 ** 9 + 7
    dp = [[0] * 13 for _ in range(s)]

    table = [[0] * 10 for _ in range(13)]
    for i in range(13):
        for j in range(10):
            table[i][j] = (i * 10 + j) % 13

    table2 = [[] for _ in range(13)]
    for i in range(13):
        for j in range(10):
            table2[table[i][j]].append(i)
    t = set(range(13))
    table2 = [t - set(i) for i in table2]

    if S[0] == -1:
        for i in range(10):
            dp[0][i] += 1
    else:
        dp[0][S[0] % 13] += 1

    for i in range(1, s):
        if S[i] == -1:
            temp = sum(dp[i - 1])
            for j in range(13):
                dp[i][j] = temp
                for k in table2[j]:
                    dp[i][j] -= dp[i - 1][k]
                dp[i][j] %= mod
        else:
            for j in range(13):
                dp[i][table[j][S[i]]] = dp[i - 1][j]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S = str(input())
S_len = len(S)

DP = [[0 for j in range(13)] for i in range(S_len + 1)]
DP[S_len][0] = 1
num = 1

for i in reversed(range(S_len)):

    

    if S[i] != "?":
        for j in range(13):
            DP[i][(j + int(S[i]) * num) % 13] += DP[i + 1][j] % 1000000007
    else:
        for j in range(13):
            for k in range(10):
                DP[i][(j + k * num) % 13] += DP[i + 1][j] % 1000000007

    num = (num * 10) % 13

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

Submission status: Accepted

Solution code:
s=input()
l=len(s)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+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:
def getlist():
	return list(map(int, input().split()))

con = 1000000007

#処理内容
def main():
	#前処理
	S = list(input())
	N = len(S)
	for i in range(N):
		if S[i] != "?":
			S[i] = int(S[i])
	S.reverse()
	
	#あまり前計算
	amari = [[0] * 6 for i in range(10)]
	for i in range(10):
		for j in range(6):
			amari[i][j] = (i * (10 ** j)) % 13

	#DP
	DP = [[0] * 13 for i in range(N + 1)]
	if S[0] == "?":
		for i in range(10):
			DP[0][i] = 1
	else:
		DP[0][S[0]] = 1
	for i in range(1, N):
		if S[i] != "?":
			A = amari[S[i]][i % 6]
			for j in range(13):
				DP[i][(A + j) % 13] += DP[i - 1][j]
				DP[i][(A + j) % 13] %= con
		else:
			for k in range(10):
				A = amari[k][i % 6]
				for j in range(13):
					DP[i][(A + j) % 13] += DP[i - 1][j]
					DP[i][(A + j) % 13] %= con

	#答え
	print(DP[N - 1][5])

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
def main():
    sts=input()
    n= len(sts)
    mod = 10**9+7
    s = []
    for c in sts:
        s.append(c)

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

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

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


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

main()

Submission status: Accepted

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    s = str(input().rstrip('\n'))
    is_first = True
    ls = [[0] * 13 for _ in range(len(s))]
    mod = 10 ** 9 + 7
    for i in range(len(s)):
        if is_first:
            is_first = False
            if s[-i-1] == "?":
                for j in range(10):
                    ls[i][j] += 1
            else:
                t = int(s[-i-1])
                ls[i][t] += 1
        else:
            mlt = pow(10, i, 13)
            if s[-i-1] == "?":
                for j in range(13):
                    for k in range(10):
                        r = (j + mlt * k) % 13
                        ls[i][r] += ls[i-1][j]
                        ls[i][r] %= mod
            else:
                t = int(s[-i-1])
                for j in range(13):
                    r = (j + mlt * t) % 13
                    ls[i][r] += ls[i-1][j]
                    ls[i][r] %= mod
    print(ls[-1][5])


if __name__ == '__main__':
    slove()

Submission status: Accepted

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

if s[0] == "?":
  ans = [1,1,1,1,1,1,1,1,1,1,0,0,0]
else:
  ans = [0,0,0,0,0,0,0,0,0,0,0,0,0]
  ans[int(s[0])] = 1


for i in s[1:]:
  dp = [0]*13
  for j in range(13):
    dp[j*10%13] = ans[j] % mod
  dp += dp
  if i == "?":
    for j in range(13):
      ans[j] = sum(dp[j+4:j+14])
  else:
    for j in range(13):
      ans[j] = dp[j+13-int(i)]
print(ans[5]%mod)

Submission status: Accepted

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

Submission status: Accepted

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

import numpy as np

MOD = 10**9 + 7

S = read().rstrip().decode('utf-8')

num = [0,0,0,0,0,0]
ques = [0,0,0,0,0,0]
for i,x in enumerate(S[::-1]):
    i %= 6
    if x == '?':
        ques[i] += 1
    else:
        num[i] += int(x)

ten = np.array([1]*10+[0,0,0],dtype=np.uint64)

def power(n):
    # (1+x+...+x^9)^n, x^13=1
    if n == 0:
        x = np.zeros(13,dtype=np.uint64)
        x[0] = 1
        return x
    x = power(n//2)
    x = np.convolve(x,x) % MOD
    x[0:12] += x[13:25]; x = x[:13]; x[x>=MOD] -= MOD
    if n&1:
        x = np.convolve(x,ten)
        x[0:12] += x[13:25]; x = x[:13]; x %= MOD
    return x

dp = [power(n) for n in ques]

pow10 = [1,10,9,12,3,4]

x = power(0)
for i,y in enumerate(dp):
    p = pow10[i]
    y[p*np.arange(13)%13] = y.copy()
    x = np.convolve(x,y) % MOD
    x[0:12] += x[13:25]; x = x[:13]; x[x>=MOD] -= MOD

n = sum(p*n for p,n in zip(pow10,num))%13

answer = x[(18-n)%13]
print(answer)

Submission status: Accepted

Solution code:
S = input()
dp = [[0]*13 for _ in range(len(S))]
if S[0]=="?":
  dp[0] = [1]*10+[0]*3
else:
  dp[0][int(S[0])] = 1
mod = 10**9+7
table = {str(i):[(10*j+i)%13 for j in range(13)] for i in range(10)}
for k in range(1,len(S)):
  tmp = dp[k-1]
  if S[k] != "?":
    for i,t in enumerate(table[S[k]]):
      dp[k][t]= tmp[i]
  else:
    for j in range(10):
      for i,t in enumerate(table[str(j)]):
        dp[k][t] += tmp[i]%mod
    dp[k] = [p%mod for p in dp[k]]
print(dp[-1][5])

Submission status: Accepted

Solution code:
def main():
    S = input()

    dp = [0] * 13
    dp[0] = 1
    MOD = 10**9 + 7

    mul = 1

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


    print(dp[5])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S = str(input())

ans = [0] * 13
ans[0] = 1
MOD = 10**9 + 7

for i in S:
    dp = [0] * 13
    for j in range(13):
        dp[(j * 10) % 13] = ans[j] % MOD
    dp += dp
    if i == '?':
        for j in range(13):
            ans[j] = sum(dp[j+4:j+14])
    else:
        for j in range(13):
            ans[j] = dp[j + 13 - int(i)]

print(ans[5] % MOD)

Submission status: Accepted

Solution code:
S = list(input())
for i in range(len(S)):
    if S[i] != '?':
        S[i] = int(S[i])
    else:
        S[i] = -1

R = [[None]*10 for i in range(13)]
for i in range(13):
    for j in range(10):
        R[i][j] = (10*i+j) % 13

Q = [[] for i in range(13)]
for j in range(10):
    for i in range(13):
        Q[R[i][j]] += [[i,j]]

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

for i in range(len(S)):
    for j in range(13):
        if S[i]!=-1:
            dp[i+1][j] += dp[i][Q[j][S[i]][0]]%1000000007
        else:
            for k in range(10):
                dp[i+1][j] += dp[i][Q[j][k][0]]%1000000007

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