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:
LARGE = 10 ** 9 + 7


def solve_a(test=False, a=2, b=16):

    if not test:
        a, b = map(int, input().split())
    if (b - a) % 2 == 0:
        print((a + b) // 2)
    else:
        print("IMPOSSIBLE")


def solve_b(test=False, n=5, p_list=[5, 2, 3, 4, 1]):

    if not test:
        n = int(input())
        p_list = list(map(int, input().split()))

    r = 0
    for i in range(n):
        if p_list[i] != i + 1:
            r += 1
    if r == 0 or r == 2:
        print("YES")
    else:
        print("NO")


def solve_c(test=False, n=2, a_list=[3, 5, 2], b_list=[4, 5]):

    if not test:
        n = int(input())
        a_list = list(map(int, input().split()))
        b_list = list(map(int, input().split()))

    res = 0
    for i in range(n):
        if b_list[i] <= a_list[i]:
            res += b_list[i]
            a_list[i] -= b_list[i]
        elif b_list[i] < a_list[i] + a_list[i + 1]:
            res += b_list[i]
            a_list[i + 1] -= b_list[i] - a_list[i]
            a_list[i] = 0
        else:
            res += a_list[i] + a_list[i + 1]
            a_list[i] = 0
            a_list[i + 1] = 0

    print(res)


def solve_d(test=False, s='??2??5'):

    if not test:
        s = input()

    l = len(s)
    res_list_new = [0] * 13
    res_list_old = [0] * 13
    zero_mod = int(s.replace('?', '0')) % 13
    res_list_new[zero_mod] += 1

    for i in range(1, l + 1):
        if s[-i] == '?':
            for k in range(13):
                res_list_old[k] = res_list_new[k] % LARGE
            base_mod = pow(10, i-1, 13)
            for j in range(1, 10):
                for k in range(13):
                    res_list_new[(k + base_mod * j) % 13] += res_list_old[k]

    print(res_list_new[5] % LARGE)


# solve_a(test=True, a=2, b=16)
# solve_a(test=True, a=0, b=3)
# solve_a(test=True, a=998244353, b=99824435)

# solve_b(test=True, n=5, p_list=[5, 2, 3, 4, 1])
# solve_b(test=True, n=5, p_list=[2, 4, 3, 5, 1])
# solve_b(test=True, n=7, p_list=[1, 2, 3, 4, 5, 6, 7])

# solve_c(test=True, n=2, a_list=[3, 5, 2], b_list=[4, 5])
# solve_c(test=True, n=3, a_list=[5, 6, 3, 8], b_list=[5, 100, 8])
# solve_c(test=True, n=2, a_list=[100, 1, 1], b_list=[1, 100])

# solve_d(test=True, s='??2??5')
# solve_d(test=True, s='?44')
# solve_d(test=True, s='7?4')
# solve_d(test=True, s='?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76???')

solve_d()

Submission status: Accepted

Solution code:
s=input()
#d=[0,1,2,3,4,5,6,7,8,9,10,11,12]
d=[[1,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0]]
t=1
p=0
for i in range(len(s)-1,-1,-1): #i->i+1,p->1-p
  #print(d[p])
  #print(t)
  c=s[i]
  if c=="?":
    for k in range(13):
      for j in range(10):
        #if d[p][k]==1:
        #  print((t*j+k)%13)
        d[1-p][(t*j+k)%13]+=d[p][k]
  else:
    x=int(c)
    for k in range(13):
      d[1-p][(k+t*x)%13]+=d[p][k]
  for k in range(13):
    d[p][k]=0
  for k in range(13):
    d[1-p][k]%=1000000007
  p=1-p
  t=t*10%13
#print(d)
print(d[len(s)%2][5])
#for i in range(10):
#  print((4+i*10)%13,(704+i*10)%13)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
s=input()
n=len(s)
n=n-1
INF=10**9+7
dp=[[0]*13 for i in range(n+1)]
dp[0][0]=1
for i in range(n):
    if s[i]=='?':
        for k in range(10):
            for j in range(13):
                dp[i+1][(10*j+k)%13]=(dp[i+1][(10*j+k)%13]+dp[i][j])%INF
    else:
        num=int(s[i])
        for j in range(13):
            dp[i+1][(10*j+num)%13]=dp[i][j]%INF
print(dp[n][5])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys, math, bisect, random, itertools
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LI()
    if (a + b) % 2:
        print("IMPOSSIBLE")
        return
    print((a + b) // 2)
    return

#B
def B():
    n = II()
    p = LI()
    for i in range(n):
        for k in range(i+1, n):
            pi = p[::1]
            pi[i], pi[k] = pi[k], pi[i]
            for j in range(n-1):
                if pi[j] > pi[j + 1]:
                    break
            else:
                print("YES")
                return
    print("NO")
    return

#C
def C():
    n = II()
    a = LI()
    b = LI()
    ans = 0
    for i in range(n):
        if a[i] >= b[i]:
            ans += b[i]
            continue
        ans += a[i]
        b[i] -= a[i]
        if a[i + 1] >= b[i]:
            ans += b[i]
            a[i + 1] -= b[i]
            continue
        ans += a[i + 1]
        a[i + 1] = 0
    print(ans)
    return

#D
def D():
    s = S()
    s = s[::-1]
    dp = [[0] * 13 for _ in range(len(s))]
    remain = 1
    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)):
        remain = (remain * 10) % 13
        dpi = dp[i]
        dpi1 = dp[i-1]
        if s[i] == "?":
            for k in range(10):
                for j in range(13):
                    dpi[(j + remain * k) % 13] += dpi1[j]
                    dpi[(j + remain * k) % 13] %= mod
        else:
            for j in range(13):
                dpi[(j + remain * int(s[i])) % 13] += dpi1[j]
    print(dp[-1][5])
    return

#E
def E():
    return

#F
def F():
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


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


def read_float():
    return float(input())


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


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


def read_str_n():
    return list(map(str, input().split()))


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


def mt(f):
    import time

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

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

    return wrap


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

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

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

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

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

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

@mt
def slv(S):
    M = Mod(10**9 + 7)
    M13 = Mod(13)
    t = [0] * 13
    t[0] = 1
    for i, c in enumerate(reversed(S)):
        if c != '?':
            n = M13.mul(M13.pow(10, i), int(c))
            nt = [0] * 13
            for k in range(13):
                nt[(k+n) % 13] = t[k]
            t = nt
        else:
            nt = [0] * 13
            for j in range(10):
                n = M13.mul(M13.pow(10, i), j)
                for k in range(13):
                    nt[(k+n) % 13] = M.add(nt[(k+n) % 13], t[k])
            t = nt
    return t[5]


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD = 10**9 + 7
S = input()[::-1]
x = 1

DP = [0]*13
DP[0] = 1
for i in range(len(S)):
    DP2 = [0]*13
    if S[i] != "?":
        s = int(S[i])
        for i in range(13):
            DP2[(i + s*x)%13] = DP[i]%MOD
    else:
        for j in range(10):
            for i in range(13):
                DP2[(i + j*x)%13] = (DP2[(i + j*x)%13] + DP[i])%MOD
    x = x*10%13
    DP = DP2

print(DP[5]%MOD)

Submission status: Accepted

Solution code:
m = int(1e9+7)
s = list(input())

dp = [[0 for _ in range(13)] for _ in range(2)]
dp[0][0] = 1
r = 1
ans = 0
for i in range(len(s)):
    for j in range(13):
        dp[(i + 1) % 2][j] = 0
    c = s[len(s) - 1 - i]
    if c == '?':
        for j in range(13):
            for k in range(10):
                dp[(i + 1) % 2][(k * r + j) % 13] += dp[i % 2][j]
    else:
        for j in range(13):
            dp[(i + 1) % 2][(int(c) * r + j) % 13] += dp[i % 2][j]
    for j in range(13):
        dp[(i + 1) % 2][j] %= m
    ans = dp[(i + 1) % 2][5]
    r *= 10
    r %= 13
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,b = LI()
    if (a-b)%2 == 0:
        print((a+b)//2)
    else:
        print("IMPOSSIBLE")
    return

#B
def B():
    n = I()
    p = LI()
    k = [p[i] for i in range(n)]
    k.sort()
    s = 0
    for i in range(n):
        s += (p[i] != k[i])
    if s < 3:
        print("YES")
    else:
        print("NO")
    return

#C
def C():
    n = I()
    a = LI()
    b = LI()
    b.append(0)
    ans = 0
    sb = sum(b)
    i = n
    while i >= 0:
        if a[i] > b[i]:
            a[i] -= b[i]
            b[i] = 0
        else:
            b[i] -= a[i]
            a[i] = 0
        if a[i] > b[i-1]:
            a[i] -= b[i-1]
            b[i-1] = 0
        else:
            b[i-1] -= a[i]
            a[i] = 0
        i -= 1

    print(sb-sum(b))
    return

#D
def D():
    s = input()
    n = len(s)
    dp = [[0]*13 for i in range(n+1)]
    f = [0]*13
    dp[0][0] = 1
    for i in range(13):
        f[i] = (i*10)%13
    for i in range(n):
        if not s[i].isdecimal():
            for j in range(13):
                for k in range(10):
                    dp[i+1][(f[j]+k)%13] += dp[i][j]
                    dp[i+1][(f[j]+k)%13] %= mod

        else:
            k = int(s[i])
            for j in range(13):
                dp[i+1][(f[j]+k)%13] += dp[i][j]
                dp[i+1][(f[j]+k)%13] %= mod

    print(dp[n][5])
    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque
import itertools
from itertools import permutations
import sys
import bisect
sys.setrecursionlimit(10**6)
#input=sys.stdin.readline
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
YNeos='YNeos'
mo=10**9+7
imp='IMPOSSIBLE'


s=input()
t=list(s)[::-1]
ans=0
dp=[0]*13
dp[0]=1
for d in range(len(t)):
    
    if t[d]=='?':
        tm=[0]*13
        for x in range(10):
            r=int(x)*pow(10,d,13)
            for i in range(13):
                tm[(i+r)%13]+=dp[i]
        dp=[j%mo for j in tm]
    else:
        tm=[0]*13
        r=int(t[d])*pow(10,d,13)
        for i in range(13):
            tm[(i+r)%13]=dp[i]
        dp=[j for j in tm]
    #print(dp)

print(dp[5]%mo)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

S=input()

digit_mod13 = 1
pats = [0]*13
buf = [0]*13

pats[0] = 1
N = len(S)
for i in range(N):
    if S[N-1-i] == '?':
        for k in range(10):
            zurasu = (k*digit_mod13) % 13
            # print(k*digit_mod13, zurasu)
            for j in range(13):
                buf[(j+zurasu)%13] += pats[j]
        for j in range(13):
            pats[j] = buf[j] % DVSR
        # flush
        for j in range(13):
            buf[j] = 0
    else:
        zurasu = (int(S[N-1-i])*digit_mod13) % 13
        for j in range(13):
            buf[(j+zurasu)%13] += pats[j]
        for j in range(13):
            pats[j] = buf[j]
        # flush
        for j in range(13):
            buf[j] = 0

    digit_mod13 = (digit_mod13*10) % 13

# print(pats)
# print(buf)

print(pats[5])

Submission status: Accepted

Solution code:
s = input()[::-1]

dp = [1] + [0] * 12
new_dp = [0] * 13

res = [[x * 10 ** i % 13 for x in range(10)] for i in range(6)]

mod = 10 ** 9 + 7

for idx, char in enumerate(s):
    new_dp = [0] * 13
    if char != "?":
        for i in range(13):
            new_i = (i + res[idx % 6][int(char)]) % 13
            new_dp[new_i] += dp[i]
        dp = new_dp
    else:
        for i in range(13):
            for j in range(10):
                new_i = (i + res[idx % 6][j]) % 13
                new_dp[new_i] += dp[i]
        dp = [x % mod for x in new_dp]

print(dp[5])

Submission status: Accepted

Solution code:
s = list(input())

MOD = 10 ** 9 + 7

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

k = 1

dp[0][0] = 1

for i, x in enumerate(reversed(s)):
    #print(i, x)
    if x == '?':
        temp = 0
        for _ in range(10):
            for j in range(13):
                m = (j+temp) % 13
                dp[i+1][m] = (dp[i+1][m] + dp[i][j]) % MOD
            temp = (temp + k) % 13
    else:
        y = int(x)
        temp = (y * k) % 13
        #print(temp)
        for j in range(13):
            m = (j + temp) % 13
            dp[i + 1][m] = (dp[i + 1][m] + dp[i][j]) % MOD
    k = (k * 10) % 13
    #print(i, x, k, dp[i+1])
    #input()

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

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

S = sys.stdin.readline().rstrip()

mods = [0] * 13
if S[-1] == '?':
    for i in range(10):
        mods[i] = 1
else:
    mods[int(S[-1])] = 1
base = 10
# 後ろから見てく
for i in range(1, len(S)):
    c = S[~i]
    if c == '?':
        aa = list(range(10))
    else:
        aa = [int(c)]
    nm = [0] * 13
    for a in aa:
        for i in range(13):
            nm[(base * a + i) % 13] += mods[i] % MOD
    mods = nm
    base *= 10
    base %= 13

print(mods[5] % MOD)

Submission status: Accepted

Solution code:
S=input()
dp=[[0]*13 for i in range(len(S)+1)]
#dp[i][k] iばんめまでであまりがｋ
dp[0][0]=1
MOD=10**9+7
L=[]
for i in range(13):
    L.append((i*10)%13)
N=len(S)
for i in range(N):
    if S[i]!="?":
        j=ord(S[i])-ord('0')
        for k in range(13):
            dp[i+1][(L[k]+j)%13]+=dp[i][k]
            dp[i+1][(L[k]+j)%13]%=MOD
    else:
        for j in range(10):
            for k in range(13):
                dp[i+1][(L[k]+j)%13]+=dp[i][k]
                dp[i+1][(L[k]+j)%13]%=MOD
print(dp[N][5])

Submission status: Accepted

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

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

if S[-1] == "?":
  for i in range(10):
    DP[0][i] = 1
else:
  t = int(S[-1])
  DP[0][t] = 1

kk = 10
for i in range(1, len(S)):
  k = kk % 13
  if S[-1 - i] == "?":
    for t in range(10):
      for j in range(13):
        DP[i][(j + k * t) % 13] += DP[i - 1][j]
        DP[i][(j + k * t) % 13] %= MOD
  else:
    t = int(S[-1 - i])
    for j in range(13):
      DP[i][(j + k * t) % 13] = DP[i - 1][j]
  kk = kk * 10 % 13

print(DP[-1][5])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    S=ST()
    #S_rev = S[::-1]
    dp = [[0]*13 for _ in range(10**5+2)] #dp[i][j]:=i-1桁目までで余りがjになる場合の数
    dp[0][0] = 1
    for i,s in enumerate(S):
        if s == "?":
            for hatena in range(10):
                for n in range(13):
                    amari = (10*n + hatena)%13
                    dp[i+1][amari] += dp[i][n]
                    dp[i+1][amari]%=mod
        else:
            for n in range(13):
                amari = (10 * n+int(s))%13

                dp[i+1][amari] += dp[i][n]
                dp[i+1][amari]%=mod
    print(dp[len(S)][5])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S = input()[::-1]
P = 10**9+7
c = 1
X = [1]+[0]*12
for s in S:
    Y = [0] * 13
    if s == "?":
        for i in range(10):
            for j in range(13):
                Y[(c*i+j)%13] += X[j]
                Y[(c*i+j)%13] %= P
    else:
        for j in range(13):
            Y[(c*int(s)+j)%13] = X[j]
            
    X = Y
    c = c*10%13

print(X[5])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
s=input()
n=len(s)
S=[]
mod = 10**9+7
M = [[0 for i in range(10)] for j in range(n)]

for i in range(10):
    M[0][i] = i
for i in range(1, n):
    for j in range(10):
        M[i][j] = (M[i-1][j] * 10) % 13

#print(M)

for i in range(n):
    if s[-i-1]=="?":
        S.append("?")
    else:
        S.append(int(s[-i-1]))

#print(S)

DP = [[0 for i in range(13)] for j in range(n)]

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] == "?":
        for j in range(10):
            for k in range(13):
                DP[i][(k+M[i][j])%13] += DP[i-1][k]%mod
    else:
        j=S[i]
        for k in range(13):
            DP[i][(k+M[i][j])%13] += DP[i-1][k]%mod

    #print(DP)

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

Submission status: Accepted

Solution code:
S = list(input())
S = [int(s) if s != "?" else -1 for s in S]
mod = [1]
for i in range(10**5 + 1):
	mod.append((mod[i] * 10) % 13)
MOD = 10**9 + 7
N = len(S)
dp = [[0 for j in range(13)] for i in range(N)]
for i in range(N):
	d = S[N-1 - i]
	for x in range(10):
		if d == x or d == -1:
			plus = (mod[i] * x) % 13
			if i == 0:
				dp[i][x] = 1
			else:
				for j in range(13):
					J = (j+plus) % 13
					dp[i][J] = (dp[i][J] + dp[i-1][j]) % MOD
print(dp[N-1][5])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def solve(S: str):
    N = len(S)
    r_d = [1] * (N+1)
    r_d[0] = 0
    for i in range(2, N+1):
        r_d[i] = (r_d[i-1] * 10) % 13
    
    dp = [[0 for j in range(N+1)] for i in range(13)] # dp[i][j]: 13でわってiになるSのj桁目まで数の総数
    dp[0][0] = 1

    for j in range(1, N+1):
        d = S[-j]
        if d != "?":
            d = (int(d) * r_d[j]) % 13
            for i in range(13):
                dp[i][j] += dp[(i - d) % 13][j-1]
            continue
        for k in range(10):
            d = (k * r_d[j]) % 13
            for i in range(13):
                dp[i][j] += dp[(i - d) % 13][j-1]
                dp[i][j] %= MOD
    print(dp[5][N])
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

for i in range(n):
    if s[i] == "?":
        tmp = keta[i]
        for j in range(10):
            for k in range(13):
                dp[i + 1][(j*tmp + k) % 13] += dp[i][k]
                dp[i + 1][(j*tmp + k) % 13] %= MOD
    else:
        num = int(s[i])
        tmp = keta[i]
        for k in range(13):
            dp[i + 1][(num*tmp + k) % 13] += dp[i][k]
            dp[i + 1][(num*tmp + k) % 13] %= MOD        
print(dp[n][5])

Submission status: Accepted

Solution code:
S = input()
N = len(S)
su = 0
L = [0]*13
L[0] = 1
M = [1, 10, 9, 12, 3, 4]
mod = 10**9+7
for i, c in enumerate(S[::-1]):
    m = M[i % 6]
    if c=="?":
        Lc = L[:]
        for j in range(m, m*10, m):
            for k in range(13):
                idx = (k+j)%13
                L[idx] = (L[idx] + Lc[k]) % mod
    else:
        su += int(c) * m
print(L[(-su+5)%13])

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
S = S[::-1]
for i in range(N):
    if S[i] != '?':
        m = int(S[i])
        rm = (m*pow(10,i,13))%13
        for r in range(13):
            dp[i+1][(r+rm)%13] = dp[i][r]
            dp[i+1][(r+rm)%13] %= mod
    else:
        for m in range(10):
            rm = (m*pow(10,i,13))%13
            for r in range(13):
                dp[i+1][(r+rm)%13] += dp[i][r]
                dp[i+1][(r+rm)%13] %= mod

print(dp[N][5])

Submission status: Accepted

Solution code:
S = input()

S = S[::-1]

mod_list = [pow(10,i,13) for i in range(12)]
mod = 10**9 + 7
DP = [[0]*13 for i in range(len(S)+1)]
DP[0][0] = 1

for i in range(len(S)):
    if S[i]=='?':
        for j in range(10):
            for k in range(13):
                DP[i+1][(k+j*mod_list[i%12])%13] = (DP[i+1][(k+j*mod_list[i%12])%13] + DP[i][k])%mod
    else:
        s=int(S[i])
        for k in range(13):
            DP[i+1][(k+s*mod_list[i%12])%13] =(DP[i+1][(k+s*mod_list[i%12])%13] + DP[i][k])%mod

print(DP[len(S)][5])

Submission status: Accepted

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

data = [0 for i in range(n+2)] #10**iを13で割ったあまり
data[0] = 1
for i in range(1,n+2):
    data[i] = (data[i-1]*10)%13


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

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


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

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

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

s = input()
l = len(s)
MOD = 10**9+7

dp = [0]*13
dp[0] = 1
for i in s:
    new = [0]*13
    if i == "?":
        for i in range(10):
            for j in range(13):
                new[(10*j+i)%13] += dp[j]
    else:
        i = int(i)
        for j in range(13):
            new[(i+10*j)%13] += dp[j]
    
    for i in range(13):
        new[i] %= MOD
    dp,new = new,dp
#    print(dp)

print(dp[5]%MOD)

Submission status: Accepted

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

mod = 10**9 + 7

for i in range(n):
    c = s[i]
    if c == '?':
        V = [0,1,2,3,4,5,6,7,8,9]
    else:
        V = [int(c)]
    for v in V:
        d = v*pow(10, n-i-1, 13)%13
        for j in range(13):
            dp[i+1][(j+d)%13] += dp[i][j]

    for j in range(13):
        dp[i+1][j%13] %= mod

print(dp[n][5])

Submission status: Accepted

Solution code:
def find(S):
    MOD=10**9+7
    S=S[::-1]
    dp=[[0]*13 for i in range(len(S))]
    power=1
    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)):
        power*=10
        power%=13
        if S[i]=="?":
            for j in range(13):
                for k in range(10):
                    dp[i][j]+=dp[i-1][(j-power*k)%13]
                    dp[i][j]%=MOD
        else:
            for j in range(13):
                k=int(S[i])
                dp[i][j]+=dp[i-1][(j-power*k)%13]
                dp[i][j]%=MOD              
    return dp[-1][5]

S=input()
print(find(S))

Submission status: Accepted

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



dp = [0] * 13
dp[0] = 1
for s in S :
    dp_ = [0] * 13
    if s == '?' :
        for i in range(13) :
            for j in range(10) :
                dp_[(i*10+j)%13] += dp[i]
                dp_[(i*10+j)%13] %= MOD
    else :
        s = int(s)
        for i in range(13) :
            dp_[(i*10+s)%13] += dp[i]
            dp_[(i*10+s)%13] %= MOD
    dp = dp_
            
print(dp[5])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  # type: int

def solve(S: str):
    N = len(S)
    dp = [[0] * 13 for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(N):
        for j in range(13):
            if S[i] == '?':
                for k in range(10):
                    nex = (j * 10 + k) % 13
                    dp[i + 1][nex] += dp[i][j]
                    dp[i + 1][nex] %= MOD
            else:
                k = int(S[i])
                nex = (j * 10 + k) % 13
                dp[i + 1][nex] += dp[i][j]
                dp[i + 1][nex] %= MOD
    ret = dp[N][5]
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S = [int(s) if s != '?' else -1 for s in input().strip()]
mod = 10**9+7
dp = [0]*13
dp[0] = 1
cnt = 1
for i, s in enumerate(S[::-1]): 
    d = [0]*13
    if s == -1:
        for j in range(10):
            for k in range(13):
                d[(j*cnt+k)%13] = (d[(j*cnt+k)%13] + dp[k])%mod
    else:
        for k in range(13):
            d[(s*cnt+k)%13] = (d[(s*cnt+k)%13] + dp[k])%mod
    cnt = (cnt*10)%13
    dp = d[:]
print(dp[5])

Submission status: Accepted

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

Submission status: Runtime Error

Solution code:
def f(i,k):
  for j in range(13):
    dp[i+1][(j*10+k)%13]+=dp[i][j]
    dp[i+1][(j*10+k)%13]%=mod
  
mod=10**9+7
s=input()
n=len(s)
dp=[[0]*13 for i in range(10**5)]
dp[0][0]=mul=1

for i in range(n):
  if s[i]=='?':
    for k in range(10):
      f(i,k)
  else:
    f(i,int(s[i]))
  
print(dp[n][5]%mod)