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()
n = len(S)
x = 10 ** 9 + 7
a = [1,0,0,0,0,0,0,0,0,0,0,0,0]

c = [1, -3, -4, -1, 3, 4]
for i in range(n):
    b = [0] * 13
    p = i % 6
    if S[n - i - 1] == "?":
        for j in range(13):
            for k in range(10):
                b[j] += a[(j - c[p] * k) % 13]
            b[j] = b[j] % x
        a = b
    else:
        s = int(S[n - i - 1])
        for j in range(13):
            b[j] = a[(j - c[p] * s) % 13]
        a = b
print(a[5])

Submission status: Accepted

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

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

dp[0] = 1
for i in range(N):
    pp, dp = dp, pp
    for d in range(13):
        dp[d] = 0
    s = S[N-i-1]
    b = pow(10, i, 13)
    if s == '?':
        for d in range(13):
            for e in range(10):
                dp[(d+b*e)%13] += pp[d]
                dp[(d+b*e)%13] %= MOD
    else:
        s = int(s)
        for d in range(13):
            dp[(d+b*s)%13] += pp[d]
            dp[(d+b*s)%13] %= MOD

print(dp[5])

Submission status: Accepted

Solution code:
m=10**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(10):
      r=int(x)*pow(10,d,k)
      for i in range(k):
        p[(i+r)%k]+=dp[i]
  else:
    r=int(t[d])*pow(10,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:
S = input()
Ls = [1, 10, 9, 12, 3, 4]  # 10^n % 13, n % 6でループ
C = 10 ** 9 + 7

L = len(S) - 1
mem = [[0 for _ in range(13)] for _ in range(len(S))]
if S[L] == '?':
    for m in range(10):
        mem[0][m] = 1
else:
    mem[0][int(S[L])] = 1

for i in range(1, len(S)):
    t = S[L - i]
    for m in range(13):
        if t == '?':
            s = 0
            for j in range(10):
                tm = m - ((Ls[i % 6] * j) % 13)
                if tm < 0:
                    tm += 13
                s += mem[i - 1][tm]
            mem[i][m] = s % C
        else:
            tm = m - ((Ls[i % 6] * int(t)) % 13)
            if tm < 0:
                tm += 13
            mem[i][m] = mem[i - 1][tm] % C
print(mem[len(S) - 1][5])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict

def main():
    data = list(input())
    mod = 10 ** 9 + 7

    q_num = data.count('?')

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

    for i in range(1, len(data) + 1):
        now_ele = data[i - 1]
        if now_ele == '?':
            for j in range(13):
                for k in range(10):
                    amari = (j * 10 + k) % 13
                    dp[i][amari] += dp[i - 1][j]
                    dp[i][amari] %= mod
        else:
            now_ele = int(now_ele)
            for j in range(13):
                amari = (j * 10 + int(now_ele)) % 13
                dp[i][amari] += dp[i - 1][j]
                dp[i][amari] %= mod
        # print(dp[i])

    ans = dp[len(data)][5]
    print(ans)



if __name__ == '__main__':
    main()
    # test()

Submission status: Accepted

Solution code:
import sys

MOD = 1000000007


def main():
    s = sys.stdin.readline().strip()
    dp = [[0] * 13 for _ in range(len(s))]

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

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S = list(input())[::-1]
Now = [0 for _ in range(13)]
Next = [0 for _ in range(13)]

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
 
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
 
MOD = 10 ** 9 + 7
s = input().strip()
n = len(s)
if s[-1] == "?":
    tmp = [1 for i in range(10)] + [0 for i in range(3+13*(n-1))]
 
else:
    tmp = [0 for i in range(13*n)]
    # print("-------------------")
    # print(s[-1])
    # print(int(s[-1]))
    tmp[int(s[-1])] = 1
# print(len(tmp))
keta = 1
for kt, c in enumerate(s[::-1][1:]):
    keta = (keta * 10) % 13
    
    if c != "?":
        seni = int(c) * keta
        for j in range(13):
            tmp[(j + seni) % 13 + (kt + 1) * 13] += tmp[kt * 13 + j] % MOD
    else:
        for isure in range(10):
            seni = isure * keta
            for j in range(13):
                tmp[(j + seni) % 13 + (kt + 1) * 13] += tmp[kt * 13 + j] % MOD
                # print(nw)
 
    # print(tmp[(13*kt):13*(kt+1)])
    # tmp = [num % MOD for num in nw]
    # tmp = nw
print(tmp[-8] % MOD)

Submission status: Accepted

Solution code:
import sys

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    T = list(str(input().strip()))
    S = [int(t) if t != '?' else -1 for t in T]
    n = len(S)

    dp = [[0] * 13 for _ in range(n)]
    s = S.pop()
    if s < 0:
        for i in range(10):
            dp[0][i] = 1
    else:
        dp[0][s] = 1

    digit = 1
    m = 1
    while S:
        s = S.pop()
        m = (m * 10) % 13
        if s < 0:
            for k in range(10):
                M = (m * k) % 13
                for i in range(13):
                    j = (i + M) % 13
                    dp[digit][j] += dp[digit-1][i]
                    dp[digit][j] %= MOD
        else:
            M = (m * s) % 13
            for i in range(13):
                j = (i + M) % 13
                dp[digit][j] += dp[digit-1][i]
                dp[digit][j] %= MOD
        digit += 1

    return dp[n-1][5]


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

Submission status: Accepted

Solution code:
import sys
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
sys.setrecursionlimit(int(1e+6))
MOD = int(1e+9) + 7
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3

def main():
    S = i2s()
    nn09 = [i for i in range(10)]
    #rot = [(i*10)%13 for i in range(10)]    # [0, 10, 7, 4, 1, 11, 8, 5, 2, 12]
    DP = [0] * 13
    # 初期化
    if S[-1] == '?':
        for i in nn09:
            DP[i] = 1
    else:
        DP[int(S[-1])] = 1
    d = 10
    for i in range(len(S)-2, -1, -1):
        dp2 = [0] * 13
        s = S[i]
        if s == '?':
            nn = nn09
        else:
            nn = [int(s)]
        for n in nn:
            for j in range(13):
                k = (d*n+j) % 13
                dp2[k] = (dp2[k] + DP[j]) % MOD
        DP = dp2
        d = (d*10) % 13

    #print(DP)
    print(DP[5])

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
MOD = 10**9 + 7
s = list(input())[::-1]
n = len(s)
dp = [[0] * 13 for _ in range(len(s) + 1)]
if s[0] == '?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(s[0])] = 1
for i in range(n - 1):
    if s[i + 1] == '?':
        for k in range(13):
            for l in range(10):
                dp[i + 1][(k + l * 10**((i + 1) % 6)) % 13] += dp[i][k]
                dp[i + 1][(k + l * 10**((i + 1) % 6)) % 13] %= MOD

    else:
        for k in range(13):
            dp[i + 1][(k + int(s[i + 1]) * 10**((i + 1) % 6)) % 13] += dp[i][k]
            dp[i + 1][(k + int(s[i + 1]) * 10**((i + 1) % 6)) % 13] %= MOD
print(dp[n - 1][5])

Submission status: Accepted

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

    if s[n-1] == -1:
        for j in range(10):
            dp[0][j] = 1
    else:
        dp[0][s[n-1]] = 1
    i10 = 1
    for i in range(1, n):
        i10 = (10 * i10) % 13
        c = s[n-i-1]
        for k in range(13):
            if c == -1:
                for j in range(10):
                    m = (i10 * j + k) % 13
                    dp[i][m] += dp[i-1][k]
                    dp[i][m] %= MOD
            else:
                m = (i10 * c + k) % 13
                dp[i][m] += dp[i-1][k]
                dp[i][m] %= MOD
    print(dp[n-1][5])


main()

Submission status: Accepted

Solution code:
words = lambda t : list(map(t, input().split()))
s = input()
rs = reversed(s)

a = []
cur_mod_10_pow = 1
v = 0
for i,c in enumerate(rs):
    if c == "?":
        a.append(cur_mod_10_pow)
    else:
        v += (int(c) * cur_mod_10_pow) % 13
        v %= 13
    cur_mod_10_pow *= 10
    cur_mod_10_pow %= 13

#print(v, list(reversed(a)))
MOD = 1000000007
prev = [0] * 13
prev[0] = 1
#print(prev)
for aa in a:
    cur = [0 for _ in range(13)]
    for i,p in enumerate(prev):
        #print(i,p, cur)
        for j in range(10):
            #print(i,j,(i+aa*j) % 13)
            cur[(i+(aa*j)) % 13] += p
            cur[(i+aa*j) % 13] %= MOD
    #print(cur)
    prev = cur

print(prev[(5-v)%13])

Submission status: Accepted

Solution code:
def li():
    return list(map(int, input().split()))


if __name__ == "__main__":
    s = input()
    ques_count = s.count('?')
    base_num = 1
    rem_list = []
    for _ in range(len(s)):
        rem_list.append(base_num % 13)
        base_num = base_num * 10 % 13
    rem_list = rem_list[::-1]

    rem1 = 0
    for index, si in enumerate(s):
        if si != '?':
            si_int = int(si)
            rem1 = rem1 + si_int * rem_list[index]
    rem1 = rem1 % 13

    dp = [[0] * 13 for _ in range(ques_count + 1)]
    dp[0][rem1] = 1
    dp_index = 1
    for index, si in enumerate(s):
        if si == '?':
            rem_cdd_list = [rem_list[index] * i % 13 for i in range(10)]
            for rem in rem_cdd_list:
                for i in range(13):
                    dp[dp_index][i] = (dp[dp_index][i] + dp[dp_index - 1][(i - rem) % 13]) % (10 ** 9 + 7)
            dp_index = dp_index + 1
    # print(dp)
    print(dp[ques_count][5])

# 各桁について13で割ったときの余りを求めておく
# 確定した桁に対する余りを求める

# 0,1,2  0,3,4  0,5,6 i番目の?までを使って余りをjにできる場合数
# (a-i) mod d = (a mod d - i mod d) mod d = (a mod d - i) mod d

Submission status: Accepted

Solution code:
M=10**9+7
#リストに入力（文字列）
text=input()
lst=list(text)
lst.reverse()
digit=len(lst)
six=[[0,0],[0,0],[0,0],[0,0],[0,0],[0,0]]
for i in range(digit):
  if(lst[i]=="?"):
    six[i%6][1]=six[i%6][1]+1
  else:
    six[i%6][0]=(six[i%6][0]+int(lst[i]))%13
rem=-(six[0][0]+10*six[1][0]+9*six[2][0]+12*six[3][0]+3*six[4][0]+4*six[5][0]-5)%13
######(?のいじったもの)+rem=0(mod13)
######(?*1+?*10+?*9+?*12+?*3+?*4)+rem=0
modulos=[1,0,0,0,0,0,0,0,0,0,0,0,0]
def mat1(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i-1)%13]+ls[(i-2)%13]+ls[(i-3)%13]+ls[(i-4)%13]+ls[(i-5)%13]+ls[(i-6)%13]+ls[(i-7)%13]+ls[(i-8)%13]+ls[(i-9)%13])%M
  return val_ls
def mat10(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i-10)%13]+ls[(i-20)%13]+ls[(i-30)%13]+ls[(i-40)%13]+ls[(i-50)%13]+ls[(i-60)%13]+ls[(i-70)%13]+ls[(i-80)%13]+ls[(i-90)%13])%M
  return val_ls
def mat100(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i-9)%13]+ls[(i-18)%13]+ls[(i-27)%13]+ls[(i-36)%13]+ls[(i-45)%13]+ls[(i-54)%13]+ls[(i-63)%13]+ls[(i-72)%13]+ls[(i-81)%13])%M
  return val_ls
def mat1000(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i+1)%13]+ls[(i+2)%13]+ls[(i+3)%13]+ls[(i+4)%13]+ls[(i+5)%13]+ls[(i+6)%13]+ls[(i+7)%13]+ls[(i+8)%13]+ls[(i+9)%13])%M
  return val_ls
def mat10000(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i-3)%13]+ls[(i-6)%13]+ls[(i-9)%13]+ls[(i-12)%13]+ls[(i-15)%13]+ls[(i-18)%13]+ls[(i-21)%13]+ls[(i-24)%13]+ls[(i-27)%13])%M
  return val_ls
def mat100000(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i-4)%13]+ls[(i-8)%13]+ls[(i-12)%13]+ls[(i-16)%13]+ls[(i-20)%13]+ls[(i-24)%13]+ls[(i-28)%13]+ls[(i-32)%13]+ls[(i-36)%13])%M
  return val_ls
for j in range(six[0][1]):
  modulos=mat1(modulos)
for j in range(six[1][1]):
  modulos=mat10(modulos)
for j in range(six[2][1]):
  modulos=mat100(modulos)
for j in range(six[3][1]):
  modulos=mat1000(modulos)
for j in range(six[4][1]):
  modulos=mat10000(modulos)
for j in range(six[5][1]):
  modulos=mat100000(modulos)
print(modulos[rem])

Submission status: Accepted

Solution code:
inf = 10 ** 18
P = 10 ** 9 + 7

S = input()
N = len(S)

tmp = 1
modrow = [1] * 6
for i in range(5):
    tmp = (tmp * 10) % 13
    modrow[1 + i] = tmp

modtab = [[None] * 10 for i in range(6)]
for i in range(6):
    for j in range(10):
        modtab[i][j] = (modrow[i] * j) % 13

# for modcol in modtab:
#     print("#", sorted(modcol))

# X + question === 5 (mod 13)
X = 0
q_idx = []
for i, Si in enumerate(S[::-1]):
    if Si == '?':
        q_idx.append(i)
    else:
        X = (X + modtab[i % 6][int(Si)]) % 13


M = len(q_idx)
ans_tab = [[0] * 13 for _ in range(M + 1)]

ans_tab[0][0] = 1
for i, idx in enumerate(q_idx):
    for src in range(13):
        for coeff in range(10):
            dst = (src + modtab[idx % 6][coeff]) % 13
            ans_tab[1 + i][dst] = (ans_tab[1 + i][dst] + ans_tab[i][src]) % P
        
# print("#", ans_tab[-1])
idx_ans = (5 - X) % 13
print(ans_tab[-1][idx_ans])

Submission status: Accepted

Solution code:
s=list(input())
s.reverse()
l=[1,10,9,12,3,4]
p=10**9+7
dp=[[0 for i in range(13)] for j in range(len(s))]
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)):
  if s[i]!='?':
    for j in range(13):
      dp[i][j]+=dp[i-1][(j-(int(s[i])*l[i%6]))%13]
      dp[i][j]%=p
  else:
    for j in range(13):
      for k in range(10):
        dp[i][j]+=dp[i-1][(j-k*l[i%6])%13]
        dp[i][j]%=p
print(dp[len(s)-1][5])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from functools import lru_cache

PRIME = 10 ** 9 + 7


@lru_cache(maxsize=None)
def digitmod13(y):
    if y == 0:
        return 1
    elif y == 1:
        return 10 % 13
    elif y % 2 == 0:
        return digitmod13(y // 2) ** 2 % 13
    else:
        return digitmod13(y // 2) ** 2 * 10 % 13


def main():
    S = input()
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(N)]
    S = S[::-1]
    
    # init
    first = S[0]
    if first == '?':
        for k in range(10):
            dp[0][k] = 1
    else:
        first = int(first)
        dp[0][first] = 1
    
    # prepare table
    table = [[[(i + (j * k)) % 13 for k in range(13)] for j in range(10)] for i in range(13)]
    
    # dp
    for i in range(1, N):
        c = S[i]
        if c == '?':
            for d in range(13):
                for k in range(10):
                    mod = table[d][k][digitmod13(i)]
                    dp[i][mod] += dp[i - 1][d]
                    dp[i][mod] %= PRIME
        else:
            c = int(c)
            for d in range(13):
                mod = table[d][c][digitmod13(i)]
                dp[i][mod] += dp[i - 1][d]
                dp[i][mod] %= PRIME
    
    print(dp[N - 1][5] % PRIME)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

rs = [[0] * 10 for i in range(len(S))]
for i in reversed(range(len(S))):
    if i == len(S) - 1:
        for j in range(10):
            rs[i][j] = j % 13
        continue

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


for i in reversed(range(len(S))):
    if i == len(S) - 1:
        if S[i] == '?':
            for v in range(10):
                r = v % 13
                dp[i][r] += 1
        else:
            v = int(S[i])
            r = v % 13
            dp[i][r] += 1
        continue

    if S[i] == '?':
        for v in range(10):
            for r in range(13):
                s = (rs[i][v] + r) % 13
                dp[i][s] += dp[i+1][r]
                dp[i][s] %= MOD
    else:
        v = int(S[i])
        for r in range(13):
            s = (rs[i][v] + r) % 13
            dp[i][s] += dp[i+1][r]
            dp[i][s] %= MOD

print(dp[0][5])

Submission status: Accepted

Solution code:
mod=10**9+7
s=input()
n=len(s)
R=[[[0]*13 for _ in range(10)] for __ in range(13)]
for i in range(13):
  for j in range(10):
    for k in range(13):
      R[i][j][k]=(k-i*j)%13

P=[0]*(n+1)
P[0]=1
for i in range(n):
  P[i+1]=(P[i]*10)%13

DP=[[0]*13 for _ in range(n+1)]
DP[0][0]=1
for i in range(n):
  r=P[n-1-i]
  if s[i]=="?":
    for k in range(13):
      DP[i+1][k]=sum(DP[i][R[r][j][k]] for j in range(10))
      DP[i+1][k]%=mod
  else:
    for k in range(13):
      DP[i+1][k]=DP[i][R[r][int(s[i])][k]]
      DP[i+1][k]%=mod
print(DP[n][5]%mod)

Submission status: Accepted

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

for i in range(L):
    NDP=[0]*13
    POW=pow(10,L-i-1,13)

    #print(POW)

    if S[i]=="?":
        
        for j in range(10):
            plus=POW*j%13

            for k in range(13):
                NDP[(k+plus)%13]=(NDP[(k+plus)%13]+DP[k])%mod

    else:
        plus=POW*int(S[i])%mod

        for k in range(13):
            NDP[(k+plus)%13]=(NDP[(k+plus)%13]+DP[k])%mod
        

    DP=NDP
    #print(DP)

print(DP[5])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *

mod = 10**9+7
S = input()
N = len(S)
D = [None] * N
t = 1
for i in range(N):
    D[i] = t % 13
    t = t * 10 % 13
dp = [[0] * 13 for i in range(N+1)]
if S[N-1] != '?':
    dp[N-1][int(S[N-1])] = 1
else:
    for i in range(10):
        dp[N-1][i] = 1
for k in range(N-1)[::-1]:
    d = D[N-k-1]
    for m in range(13):
        if S[k] != '?':
            dp[k][m] += dp[k+1][(m-d*int(S[k]))%13]
            dp[k][m] %= mod
        else:
            for i in range(10):
                dp[k][m] += dp[k+1][(m-i*d)%13]
                dp[k][m] %= mod
print(dp[0][5])

Submission status: Accepted

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

digit = [0] * (10**5+10)
digit[0] = 1  # digit[i] := 10**iのあまり
for i in range(1, 10**5+10):
    digit[i] = (digit[i-1] * 10) % 13

dp = [[0 for _ in range(13)] for i in range(10**5+10)]
dp[0][0] = 1

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

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

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline
Q = 10**9+7
def main():
    S = input()
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        s = S[N-1-i]
        r = pow(10, i, 13)                
        if s == '?':
            for k in range(10):
                t = k*r%13
                for j in range(13):
                    dp[i+1][(j+t)%13] = (dp[i+1][(j+t)%13] + dp[i][j])%Q
            continue
        t = int(s)*r%13
        for j in range(13):
            dp[i+1][(j+t)%13] = dp[i][j]
    print(dp[N][5])
if __name__ == '__main__':
    main()

Submission status: Accepted

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

dp = [[0] * 13 for _ in range(n + 1)]
dp[0][0] = 1
# dp[i][j] : i 文字目まで見たとき j 余る個数

for i, ss in enumerate(s, 1):
    # print(ss)
    p = pow(10, n - i, 13)
    if ss == '?':
        for c in '0123456789':
            to_add = (int(c) * p) % 13
            for r in range(13):
                dp[i][(r + to_add) % 13] += dp[i - 1][r]
                dp[i][(r + to_add) % 13] %= mod
    else:
        to_add = (int(ss) * p) % 13
        for r in range(13):
            dp[i][(r + to_add) % 13] += dp[i - 1][r]
            dp[i][(r + to_add) % 13] %= mod
print(dp[n][5])
# print(*dp[n], sep='\n')
# print(s)

Submission status: Accepted

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

p = [ (10**k)%13 for k in range(6) ]
mod_tb = [ [i*p[k]%13 for i in range(10)] for k in range(6) ]
n = [0]*6
base = 0
for k in range(len(S)):
    s = S[-(k+1)]
    if s == '?':
        n[k%6] += 1
    else:
        base += p[k%6]*int(s)
        base %= 13

DP = [ [0] * 13 for _ in range(sum(n)+1) ]
DP[0][base] = 1
i = 1
for k in range(6):
    for _ in range(n[k]):
        for m in range(13):
            for d in range(10):
                DP[i][(m + mod_tb[k][d])%13] += DP[i-1][m]
        for m in range(13):
            DP[i][m] %= MOD
        i += 1
print(DP[-1][5])

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import re
from collections import deque
import sys
import math
input = sys.stdin.readline


def int_raw():
    return int(input())


def ss_raw():
    return input().split()


def ints_raw():
    return tuple(map(int, ss_raw()))


DIV = 10**9+7


def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def ncr(n, r, mod=DIV):
	r = min(r, n-r)
	ret = 1
	for i in range(1, r+1):
		ret = ret * (n-i+1) % mod
		ret = ret * mod_inv(i, mod) % mod
	return ret


def main():
    S = input().rstrip("\n")
    dp = [[0 for i in range(13)] for i in range(len(S)+1)]
    dp [0][0] = 1
    modi = 1%13
    for i in range(1,len(S)+1):
        
        s = S[len(S)-i]
        if s!= '?':
            mod_q = (int(s)*modi)%13
            for k in range(13):
                dp[i][(k+mod_q) % 13] = (dp[i][(k+mod_q) % 13]+dp[i-1][k]) % DIV
        else:
            for j in range(10):
                mod_q = (j*modi) % 13
                for k in range(13):
                    dp[i][(k+mod_q) % 13] = (dp[i]
                                             [(k+mod_q) % 13]+dp[i-1][k]) % DIV
        modi = (modi*10)%13
    return dp[len(S)][5]
print(main())

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase

import __pypy__

MOD = 10**9 + 7


def main():
    s = input()
    t = s[::-1]

    n = len(s)

    rem = 0
    filler = []
    for i in range(n):
        if t[i] == '?':
            filler.append(pow(10, i, 13))
        else:
            rem += pow(10, i, 13) * int(t[i])

    rem %= 13

    if not filler:
        if rem == 5:
            print(1)
        else:
            print(0)
        return

    dp = [0] * 13
    for i in range(10):
        dp[i * filler[0] % 13] += 1

    for i in range(1, len(filler)):
        dp_row = [0] * 13
        for j in range(10):
            dp_row[filler[i] * j % 13] += 1

        dp_copy = [0] * 13
        for i in range(13):
            for j in range(13):
                dp_copy[(i + j) % 13] = (dp[i] * dp_row[j] + dp_copy[(i + j) % 13]) % MOD
        dp = dp_copy

    print(dp[(5 - rem) % 13])


# region fastio

BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
s = input()[::-1]
m = 13
mod = 10**9+7

r = [1]
for i in range(10**5):
    r.append(r[-1]*10 % m)

dp = [0]*m
dp[0] = 1
for i, c in enumerate(s):
    nxt = [0]*m
    if c == "?":
        for j in range(m):
            for k in range(10):
                nxt[(j+k*r[i])%m] += dp[j]
                nxt[(j+k*r[i])%m] %= mod
    else:
        n = int(c)
        for j in range(m):
            nxt[(j+n*r[i])%m] += dp[j]
            nxt[(j+n*r[i])%m] %= mod
    dp = nxt
print(dp[5])

Submission status: Accepted

Solution code:
modarr11=[77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 76]
modarr21=[8, 8, 8, 7, 8, 8, 7, 8, 8, 7, 8, 8, 7]
modarr22=[7, 8, 8, 8, 7, 8, 8, 8, 7, 8, 8, 8, 7]
modarr23=[8, 8, 8, 8, 8, 8, 8, 8, 8, 7, 7, 7, 7]
modarr31=[1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0]
modarr32=[1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1]
modarr33=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0]

s=input()
l=len(s)
if l%3!=0:
  s='0'*(3-l%3)+s
  l+=(3-l%3)
mod=10**9+7
cnt=0
dp=[[0]*13 for _ in range(l//3+1)]
for i in range(l-1,-1,-3):
  num=0
  qpos=0
  for j in range(3):
    if s[i-j]=='?':
      qpos+=1*(10**j)
    else:
      num+=int(s[i-j])*(10**j)
  if qpos==0:
    tmod=[0]*13
    tmod[num%13]=1
  elif qpos==1:
    tpos=num%13
    tmod=modarr33[-tpos:]+modarr33[:-tpos]
  elif qpos==10:
    tpos=num%13
    tmod=modarr32[-tpos:]+modarr32[:-tpos]
  elif qpos==100:
    tpos=num%13
    tmod=modarr31[-tpos:]+modarr31[:-tpos]
  elif qpos==11:
    tpos=num%13
    tmod=modarr23[-tpos:]+modarr23[:-tpos]
  elif qpos==101:
    tpos=num%13
    tmod=modarr22[-tpos:]+modarr22[:-tpos]
  elif qpos==110:
    tpos=num%13
    tmod=modarr21[-tpos:]+modarr21[:-tpos]
  elif qpos==111:
    tmod=modarr11
  if cnt==0:
    dp[1]=tmod
  elif cnt%2==0:
    for k in range(13):
      for l in range(13):
        dp[cnt+1][(k+l)%13]+=(tmod[k]*dp[cnt][l])%mod
  else:
    for k in range(13):
      for l in range(13):
        dp[cnt+1][(l-k)%13]+=(tmod[k]*dp[cnt][l])%mod
  cnt+=1
print(dp[cnt][5]%mod)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
def solve(A):
    N = len(A)
    dp = [1] + [0] * 12
    pwr = 1
    for i in xrange(N-1, -1, -1):
        if A[i] == '?':
            dp2 = [0] * 13
            for k, v in enumerate(dp):
                for d in xrange(10):
                    k2 = (k + d * pwr) % 13
                    dp2[k2] += v
                    dp2[k2] %= MOD
            dp = dp2
        else:
            shift = int(A[i]) * pwr % 13
            dp2 = [0] * 13
            for k, v in enumerate(dp):
                k2 = (k + shift) % 13
                dp2[k2] += v
            dp = dp2
        pwr *= 10
        pwr %= 13
    
    return dp[5] % MOD
        
print solve(raw_input().rstrip())

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
mod13 = [[0] * 10 for _ in range(6)]
for i in range(6):
    mod13[i] = [(10**i * item) % 13 for item in range(10)]

s = input().rstrip()
dp = [[0] * (len(s)+1) for _ in range(13)]
dp[0][0] = 1

for i, item in enumerate(s[::-1]):
    if item == "?":
        for j in range(13):
            for modval in mod13[i%6]:
                dp[(j+modval)%13][i+1] += dp[j][i]
            dp[j][i+1] %= MOD
    else:
        modval = mod13[i%6][int(item)]
        for j in range(13):
            dp[(j+modval) % 13][i+1] += dp[j][i]
            dp[j][i+1] %= MOD

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