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:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    mod = 10**9 + 7

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

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

# import bisect
# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

# from numba import jit
# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    s = input()
    d = len(s)

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

    x = s[0]
    if x == "?":
        for i in range(10):
            nummod = (i * pow(10, d - 1, 13)) % 13
            dp[0][nummod] = 1
    else:
        nummod = (int(x) * pow(10, d - 1, 13)) % 13
        dp[0][nummod] = 1

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

    print(dp[-1][5])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S = list(input())[::-1]
N = len(S)
B = [10**i % 13 for i in range(6)]

dp = [[0]*13 for i in range(N+2)]
dp[0][0] = 1
for i in range(1,N+1):
    if S[i-1] == '?':
        for j in range(10):
            for k in range(13):
                dp[i][(k+(B[(i-1)%6]*j))%13] += dp[i-1][k]
                dp[i][(k+(B[(i-1)%6]*j))%13] %= 10**9+7
    else:
        for k in range(13):
            dp[i][(k+B[(i-1)%6]*int(S[i-1]))%13] = dp[i-1][k]
print(dp[N][5])

Submission status: Accepted

Solution code:
s = input()

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

dp[0][0] = 1

for i in range(len(s)):
    ch = s[i]
    if ch == '?':
        for j in range(13):
            for k in range(10):
                dp[i+1][(10*j+k)%13] += dp[i][j]
                dp[i+1][(10*j+k)%13] %= 10 ** 9 + 7
    else:
        val = int(ch)
        for j in range(13):
            dp[i+1][(10*j+val)%13] += dp[i][j]
            dp[i+1][(10*j+val)%13] %= 10 ** 9 + 7

print(dp[-1][5])

Submission status: Accepted

Solution code:
import sys,math,copy

def main():
    # import numpy as np
    input = sys.stdin.readline
    S = ''.join(reversed(input().strip()))

    # dp = np.zeros((13), dtype=int)
    # dp_ = np.zeros((13), dtype=int)
    dp = [0] * 13
    dp_ = [0] * 13
    mod13_tuple = tuple([i % 13 for i in range(12 ** 2 + 1)])
    tuple10 = tuple(range(10))
    tuple13 = tuple(range(13))
    divisor = 10 ** 9 + 7
    dp_[0] = 1
    mul = 1
    for i in range(len(S)):
        s = S[i]
        if s == '?':
            for d in tuple10:
                m = mod13_tuple[(d * mul)]
                for pm in tuple13:
                    dp[mod13_tuple[(pm+m)]] += dp_[pm]

        else:
            si = int(s)
            m = mod13_tuple[(si * mul)]
            for pm in tuple13:
                dp[mod13_tuple[(pm+m)]] = dp_[pm]

        # dp_ = dp % divisor
        # dp = dp * 0 # np.zeros((13), dtype=int)
        for j in tuple13:
            dp_[j] = dp[j] % divisor
            dp[j] = 0
        mul = mod13_tuple[(mul * 10)]
    print(dp_[5])

main()

Submission status: Accepted

Solution code:
import sys,math,copy

def main():
    # import numpy as np
    input = sys.stdin.readline
    S = ''.join(reversed(input().strip()))

    # dp = np.zeros((13), dtype=int)
    # dp_ = np.zeros((13), dtype=int)
    dp = [0] * 13
    dp_ = [0] * 13
    mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
    list10 = list(range(10))
    list13 = list(range(13))
    divisor = 10 ** 9 + 7
    dp_[0] = 1
    mul = 1
    for i in range(len(S)):
        s = S[i]
        if s == '?':
            for d in list10:
                m = mod13_list[(d * mul)]
                for pm in list13:
                    dp[mod13_list[(pm+m)]] += dp_[pm]

        else:
            si = int(s)
            m = mod13_list[(si * mul)]
            for pm in list13:
                dp[mod13_list[(pm+m)]] = dp_[pm]

        # dp_ = dp % divisor
        # dp = dp * 0 # np.zeros((13), dtype=int)
        for j in list13:
            dp_[j] = dp[j] % divisor
            dp[j] = 0
        mul = mod13_list[(mul * 10)]
    print(dp_[5])

main()

Submission status: Accepted

Solution code:
import sys,math,copy

def main():
    # import numpy as np
    input = sys.stdin.readline
    S = ''.join(reversed(input().strip()))

    # dp = np.zeros((13), dtype=int)
    # dp_ = np.zeros((13), dtype=int)
    dp = [0] * 13
    dp_ = [0] * 13
    mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
    list10 = list(range(10))
    list13 = list(range(13))
    divisor = 10 ** 9 + 7
    dp_[0] = 1
    mul = 1
    for i in range(len(S)):
        s = S[i]
        if s == '?':
            for d in list10:
                m = mod13_list[(d * mul)]
                for pm in list13:
                    dp[mod13_list[(pm+m)]] += dp_[pm]

        else:
            si = int(s)
            m = mod13_list[(si * mul)]
            for pm in list13:
                dp[mod13_list[(pm+m)]] = dp_[pm]

        # dp_ = dp % divisor
        # dp = dp * 0 # np.zeros((13), dtype=int)
        for j in list13:
            dp_[j] = dp[j] % divisor
            dp[j] = 0
        mul = mod13_list[(mul * 10)]
    print(dp_[5])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S = list(input())
k = 0
N = len(S)
mod = 10**9+7

for i in range(N):
    if S[i] == "0":
        k += 1
    else:
        break

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

for i in range(k+1,N+1):
    for j in range(13):
        for l in range(10):
            if S[i-1] == "?" or S[i-1] == str(l):
                dp[i][(j*10+l)%13] += dp[i-1][j]
                dp[i][(j*10+l)%13] = dp[i][(j*10+l)%13] % mod
print(dp[N][5])

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

s = input()
n = len(s)

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

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

Submission status: Accepted

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

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

a=1
for i in range(1,len_s):
    a=10*a%13
    if s[-(i+1)]!='?':
        temp_S=int(s[-(i+1)])
        amari=(temp_S*a)%13
        for j in range(13):
            dp[i][(amari+j)%13]+=dp[i-1][j]%mod

    else:
        for k in range(10):
            amari=(k*a)%13
            for l in range(13):
                dp[i][(amari+l)%13]+=dp[i-1][l]%mod
#print(*dp,sep='\n')
print(dp[-1][5]%mod)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left

def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]


def main():
    S = input()
    S = [int(i) if not i == "?" else False for i in S]
    #print(S)

    S.reverse()


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

    kake = 4
    for keta, s in enumerate(S, 1):
        kake *= 10
        kake %= 13
        #print(kake)

        if s is not False:
            for i in range(13):
                idx = (i + kake * s) % 13
                dp[keta][idx] += dp[keta-1][i]

        else:
            for i in range(13):
                for j in range(10):
                    idx = (i + kake * j) % 13
                    dp[keta][idx] += dp[keta-1][i]
                    dp[keta][idx] %= mod

    #for s, i in zip(dp, S):
    #    print(sum(s) % mod)
    #    print(i)

    print(dp[len(S)][5])
    #print()
    #print(next)
    #print(next[5])


def solve():
    N, M = iip(True)
    lines = {}
    for i in range(N):
        lines[i] = []

    for i in range(M):
        a, b = iip(True)
        lines[a-1].append(b-1)
        lines[b-1].append(a-1)

    c = [[0]]
    for a in range(1, N):
        n = []
        for i in c:
            for j in range(N):
                if j in i:
                    continue
                ct = [k for k in i]
                ct.append(j)
                n.append(ct)
        c = n

    kh = []
    for i in c:
        for j in range(N):
            if j not in i:
                break
        else:
            kh.append(i)

    ans = 0
    for root in kh:
        for i in range(N):
            if i == N-1:
                ans += 1
                break
            else:
                if not root[i+1] in lines[root[i]]:
                    break

    print(ans)

#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Accepted

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

dp = [[0] * 13 for _ in range(2)]
tmp = 0
for si in s:
    if(si != '?'):
        tmp = (tmp*10 + int(si)) % 13
    else:
        tmp = tmp*10 % 13

dp[0][tmp] = 1
exp10 = 1
pointer = 0
for i,si in enumerate(s[::-1]):

    if(si!='?'):
        exp10 = exp10 * 10 % 13
        continue

    pointer = 1 - pointer
    for j in range(13):
        dp[pointer][j] = 0

    for j in range(13):
        for k in range(10):
            dp[pointer][(j + exp10*k)%13] += dp[1-pointer][j]

    for j in range(13):
        dp[pointer][j] %= mod

    exp10 = exp10 * 10 % 13

print(dp[pointer][5])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod=10**9+7
s=input()
dp1=[1]+[0]*12
for i in range(len(s)):
    dp2=[0]*13
    if s[i]!="?":
        p=int(s[i])
        for j in range(13):
            dp2[(j*10+p)%13]+=dp1[j]
    
    else:
        for p in range(10):
            for j in range(13):
                dp2[(j*10+p)%13]+=dp1[j]
    dp1=[dp2[j]%mod for j in range(13)]

print(dp1[5])

Submission status: Accepted

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

for i,s in enumerate(S):
    for j in range(13):
        if(s=="?"):
            for k in range(10):
                dp[i+1][((j*10)+k)%13] += dp[i][j]
                dp[i+1][((j*10)+k)%13]%=mod
        else:
            dp[i+1][((j*10)+int(s))%13] += dp[i][j]
            dp[i+1][((j*10)+int(s))%13]%=mod
print(dp[l][5])

Submission status: Accepted

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

MOD = 10 ** 9 + 7
dp = [[0] * 13 for _ in range(10**5+10)]
dp[0][0] = 1
for i in range(L):
    j = -1 if S[i] == "?" else int(S[i])
    if j > -1:
        # jが確定しているので、jを全探索する必要はなく、前回桁までの組み合わせの数にjを足して次のDPへ入れる
        # jが確定しているから数字の組み合わせ自体が増えるわけではない
        # そのためこれまで確定していた桁に対して、jを追加した場合のあまりを単純に移送することになる
        
        # 前回桁までの数 * 10 + j をすると、今回桁をjにしたときのあまりがわかる
        # 3?1 → 301 % 13 = 2, 30 % 13 = 4であるから、ki=4のとき、dp[i][4]の数値をdp[i+1][2]に足す
        # 30と4はmod13の世界では合同になっている
        # すなわち*10した結果である300と40も合同
        # そこにjを足した数 300+jと40+jもまた合同であると言える、ともにあまりは2
        # ここでは具体的な値である30は計算していないが、その具体的な数と合同である数字を用いて、今回桁で作成可能な数字のmodを数えているdp[i+1][2]にdp[i][4]を突っ込むことになる
        # modの世界では両辺に同じ数をかけても合同であるという性質を用いて、10をかけながら、桁ごとに数値を足していっていることになる

        for ki in range(13):
            dp[i+1][(ki * 10 + j) % 13] += dp[i][ki]
    else:
        # jが確定していないので、jになりうる値を全て試す
        # 0-9の10パターンの数字が考えられるので、全ての組み合わせ自体は*10になる
        # ? だと10パターン ??だと100パターンになるので、?が来ると、数字の組み合わせが10倍になるのは自明
        # 10**(?の数) の組み合わせの総数になる
        for j in range(10):
            for ki in range(13):
                dp[i+1][(ki * 10 + j) % 13] += dp[i][ki]
    
    for j in range(13):
        dp[i+1][j] %= MOD

print(dp[L][5])

Submission status: Accepted

Solution code:
S=input()
n=len(S)
R=[0]*13
cnt=[0]*13
Pow=[[] for i in range(6)]
mod=10**9+7

for i in range(6):
    c=10**i
    for j in range(10):
        Pow[i].append(c*j%13)
ans=0
flag=0
for i in range(n):
    if S[n-i-1]=="?":
        P=Pow[i%6]
        if flag==0:
            for p in P:
                R[p]=1
                flag=1
        else:
            for j in range(10):
                for k in range(13):
                    cnt[(k+P[j])%13]+=R[k]%mod
            R=cnt
            cnt=[0]*13
    else:
        x=int(S[n-i-1])
        ans+=Pow[i%6][x]
ans%=13
if flag==0:
    if ans==5:
        print(1)
    else:
        print(0)
else:
    print(R[(18-ans)%13]%mod)

Submission status: Accepted

Solution code:
S=input()[::-1]
l=len(S)
a=1
m=10**9+7
dp=[1]+[0]*12
for d in S:
    dp2=[0]*13
    if d=='?':
        for j in range(13):
            for k in range(10):
                dp2[(j+k*a)%13]+=dp[j]%m
    else:
        for j in range(13):
            dp2[(j+int(d)*a)%13]=dp[j]
    dp=dp2
    a=(a*10)%13 if a!=1 else 10
print(dp[5]%m)

Submission status: Accepted

Solution code:
s = input()

frommap = []
for d in range(10):
    frommap.append([0] * 13)
    for m in range(13):
        m2 = (m * 10 + d) % 13
        frommap[d][m2] = m
transmap = list(zip(*frommap))

dp = [1] + [0] * 12
for c in s:
    if c == '?':
        dp = [sum(dp[f] for f in fromlist) % 1000000007 for fromlist in transmap]
    else:
        dp = [dp[f] for f in frommap[int(c)]]

print(dp[5])

Submission status: Accepted

Solution code:
s = input()

frommap = []
for d in range(10):
    frommap.append([0] * 13)
    for m in range(13):
        m2 = (m * 10 + d) % 13
        frommap[d][m2] = m

dp = [1] + [0] * 12
for c in s:
    if c == '?':
        dp = [sum(dp[f] for f in fromlist) % 1000000007 for fromlist in zip(*frommap)]
    else:
        dp = [dp[f] for f in frommap[int(c)]]

print(dp[5])

Submission status: Accepted

Solution code:
s = input()

frommap = []
for d in range(10):
    frommap.append([0] * 13)
    for m in range(13):
        m2 = (m * 10 + d) % 13
        frommap[d][m2] = m

dp = [1] + [0] * 12
for c in s:
    if c == '?':
        dp = [sum(dp[f] for f in fromlist) % 1000000007 for fromlist in zip(*frommap)]
    else:
        f = frommap[int(c)]
        dp = [dp[f[m]] for m in range(13)]

print(dp[5])

Submission status: Accepted

Solution code:
S=input()
import numpy as np
M=13
MOD=10**9+7
dp=np.zeros(M, dtype=np.int64)
dp[0]=1
idx = np.zeros(M, dtype=np.int8)
window = np.ones(10, dtype=np.int8)
for i in range(M):
  idx[i * 10 % M] = i
for s in S:
  if s=='?':
    tdp=dp[idx]
    ndp = np.concatenate([tdp[4:], tdp])
    dp = np.convolve(ndp, window, mode='valid') % MOD
  else:
    dp=np.roll(dp[idx],int(s))
print(dp[5]%MOD)

Submission status: Accepted

Solution code:
#abc135d
s=raw_input()
mod=10**9+7
res=[0]*13
res[0]=1
for i in s:
 dp=[0]*13
 for j in range(13):
  dp[(j*10)%13]=res[j]%mod
 dp+=dp
 if i=='?':
  for k in range(13):
   res[k]=sum(dp[k+4:k+14])
 else:
  for k in range(13):
   res[k]=dp[k+13-int(i)]
print res[5]%mod

Submission status: Accepted

Solution code:
from copy import copy
MOD = int(1e9)+7

def main():
    s = input()
    n = len(s)
    dp = [0 for _ in range(13)]
    dp[0] = 1 
    mul = 1
    for i in reversed(range(n)):
        nextDP = [0 for _ in range(13)]
        if s[i] == '?':
            for j in range(13):
                for k in range(10):
                    nextDP[(k*mul + j)%13] += dp[j]
                    nextDP[(k*mul + j)%13] %= MOD
        else:
            x = ord(s[i]) - ord('0')
            for j in range(13):
                nextDP[(x*mul + j)%13] += dp[j]
                nextDP[(x*mul + j)%13] %= MOD
        dp = copy(nextDP)
        mul *= 10
        mul %= 13
    print(dp[5])
main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

S = input()
S = S[::-1]
LS = len(S)

MOD = 10 ** 9 + 7


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

for i in range(LS):
    if S[i] != '?':
        d = int(S[i])
        md = (d * pow(10, i, 13)) % 13

        if md == 0:
            dp[i + 1] = dp[i]
        else:
            dp[i + 1][md:] = dp[i][:-md]
            dp[i + 1][:md] = dp[i][-md:]
    else:
        t = pow(10, i, 13)
        for k in range(10):
            md = (k * t) % 13

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

print(dp[LS][5])

Submission status: Accepted

Solution code:
import copy
s=input()
a=0
n=len(s)
x=[0]*13
if s[-1]=='?':
  x = [int(i<=9) for i in range(13)]
else:
  x[int(s[-1])%13]=1
p=1
for i in range(1,n):
  p=10*p%13
  y=[0]*13
  if s[n-1-i]=='?':
    for j in range(13):
      for k in range(10):
        y[(k*p+j)%13]+=x[j]
  else:
    t=int(s[n-1-i])
    for j in range(13):
      y[(t*p+j)%13]+=x[j]
  x=copy.deepcopy(y)
  x = [z%(10**9+7) for z in x]
print(x[5])

Submission status: Accepted

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

# dp[逆順i桁][j mod 13] := 総数
dp = [[0]*13 for _ in range(len(s)+1)]
dp[0][0] = 1
mul = 1
s_rev = s[::-1]
for i in range(len(s)):
    x = s_rev[i]
    if x == '?':
        for k in range(10):
            for j in range(13):
                dp[i+1][(mul*k+j)%13] += dp[i][j]
                dp[i+1][(mul*k+j)%13] %= mod
    else:
        k = int(x)
        for j in range(13):
            dp[i+1][(mul*k+j)%13] += dp[i][j]
            dp[i+1][(mul*k+j)%13] %= mod
    mul = mul * 10 % 13

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
s = input()
s = s[::-1]
MOD = 10**9+7
mod13_map = [[i for i in range(13)]]
ma = mod13_map.append
for i in range(1,10**5):
    next_digit = list(map(lambda x:x*10%13,mod13_map[i-1]))
    ma(next_digit)

ret = [1] + [0] * 12 #13で割ってi余る数の合計
for i,v in enumerate(s):
    if v!="?":
        #mod13_map[i][v]だけ、右にシフト
        ret *= 2
        sft = mod13_map[i][int(v)]
        ret = ret[13-sft:26-sft]
    else:
        temp_ret = [0] * 13
        for j in range(10):
            #?がjの場合
            for k,l in enumerate(ret):
                temp_ret[(k+mod13_map[i][j])%13]+=l
        temp_ret = list(map(lambda x:x%MOD,temp_ret))
        ret = temp_ret
print(ret[5]%MOD)

Submission status: Accepted

Solution code:
mod = 10**9 + 7


s = input()

n = len(s)
DP = [[0] * 13 for _ in range(n + 1)]

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

print(DP[n][5])

Submission status: Accepted

Solution code:
import sys

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

MOD = 10 ** 9 + 7
S = sr()
# 桁DP, 上から
dp = [0] * 13
dp[0] = 1
for s in S:
    prev = [x for x in dp]
    num = s
    dp = [0] * 13
    if num != '?':
        num = int(num)
        for j in range(13):
            dp[(10*j+num)%13] = prev[j]
    else:
        for j in range(13):
            for k in range(10):
                dp[(10*j+k)%13] += prev[j]
    dp = [x%MOD for x in dp]

answer = dp[5]
print(answer%MOD)

Submission status: Accepted

Solution code:
import sys

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

MOD = 10 ** 9 + 7
S = sr()
# 桁DP, 上から
dp = [0] * 13
dp[0] = 1
for s in S:
    prev = [x for x in dp]
    dp = [0] * 13
    if s != '?':
        s = int(s)
        for j in range(13):
            dp[(10*j+s)%13] = prev[j]
    else:
        for j in range(13):
            for k in range(10):
                dp[(10*j+k)%13] += prev[j]
    dp = [x%MOD for x in dp]

answer = dp[5]
print(answer%MOD)

Submission status: Accepted

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

dp = [0]*13
dp[0] = 1
r = 1
for c in S[::-1]:
    dp2 = [0]*13
    for p in range(13):
        if c =='?':
            for d in range(10):
                k = (d*r+p)%13
                dp2[k] += dp[p]
        else:
            d = int(c)
            k = (d*r+p)%13
            dp2[k] += dp[p]
    for k in range(13):
        dp2[k] %= MOD
    r *= 10
    r %= 13
    dp = dp2
print(dp[5])

Submission status: Accepted

Solution code:
S = input()
dp = [[0] * 13 for _ in range(10 ** 5 + 5)]
MOD = 10 ** 9 + 7
dp[0][0] = 1
n = len(S)
for i in range(n):
    if S[i] == "?":
        c = -1
    else:
        c = int(S[i])

    for j in range(10):
        if c != -1 and c != j:
            continue
        for ki in range(13):
            dp[i + 1][(ki * 10 + j) % 13] += dp[i][ki]

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

print(dp[n][5])

Submission status: Accepted

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

for i in range(1,N+1):
    R = [0]*13
    if S[i-1] == "?":
        for j in range(10):
            r = j * pow(10,N-i,13) %13 
            R[r] += 1 

    else:
        r = int(S[i-1]) * pow(10,N-i,13) %13
        R[r] += 1

    for k in range(13):
                for l in range(13):
                    dp[i][k] += dp[i-1][l] * R[(k-l)%13]
                    dp[i][k] %= MOD

print(dp[N][5])

Submission status: Accepted

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

for i in range(1,N+1):
    R = [0]*13
    if S[i-1] == "?":
        for j in range(10):
            r = j * pow(10,N-i,13) %13 
            R[r] += 1 
        for k in range(13):
            for l in range(13):
                    dp[i][k] += dp[i-1][l] * R[(k-l)%13]
                    dp[i][k] %= MOD

    else:
        r = int(S[i-1]) * pow(10,N-i,13) %13
        R[r] += 1
        for k in range(13):
                for l in range(13):
                    dp[i][k] += dp[i-1][l] * R[(k-l)%13]
                    dp[i][k] %= MOD

print(dp[N][5])

Submission status: Accepted

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

dp = [[0] * 13 for i in range(n + 1)]
dp[0][0] = 1
for i in range(n, ):
    keta = pow(10, n - i - 1, MOD)
    if s[i] == "?":
        for si in range(10):
            for j in range(MOD):
                dp[i + 1][(j + si * keta) % MOD] += dp[i][j]
                dp[i + 1][(j + si * keta) % MOD] %= MOD2
    else:
        for j in range(MOD):
            dp[i + 1][(j + int(s[i]) * keta) % MOD] += dp[i][j]
            dp[i + 1][(j + int(s[i]) * keta) % MOD] %= MOD2
print(dp[-1][5])

Submission status: Accepted

Solution code:
S = input()
N = len(S)
S = list(S)
S.reverse()

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

print(dp[N][5])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
D - Digits Parade
https://atcoder.jp/contests/abc135/tasks/abc135_d

"""
import sys


def solve(S):
    dp = [[0] * 13 for _ in range(len(S)+1)]
    dp[0][0] = 1
    for i, ch in enumerate(S):
        for j in range(10):
            if ch == '?' or j == int(ch):
                for ki in range(13):
                    dp[i+1][(ki*10 + j) % 13] += dp[i][ki]
        for j in range(13):
            dp[i+1][j] %= (10**9 + 7)
    return dp[len(S)][5]


def main(args):
    S = input()
    ans = solve(S)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

S = list(input())
N = len(S)

# dp[i][j] ... S[:i]でj(mod13)をつくる組み合わせの数
dp = [[0] * 13 for _ in range(N + 1)]

dp[0][0] = 1
for i in range(1, N + 1):
    if S[i - 1] == '?':
        for j in range(13):
            for k in range(10):
                dp[i][(j * 10 + k) % 13] += dp[i - 1][j]
    else:
        x = ord(S[i - 1]) - ord('0')
        for j in range(13):
            dp[i][(j * 10 + x) % 13] += dp[i - 1][j]
    for j in range(13):
        dp[i][j] %= 1000000007
print(dp[-1][5])

Submission status: Accepted

Solution code:
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd
import sys
#input = sys.stdin.readline

import copy
"""
from collections import *
S=input()
dp=[[0 for i in range(13)] for m in range(len(S))]
mod=10**9+7
if S[0]=="?":
    for i in range(10):
        dp[0][i]+=1
else:
    dp[0][int(S[0])]+=1
for i in range(1,len(S)):
    for m in range(13):
        if S[i]=="?":
            for j in range(10):
                dp[i][(m*10+j)%13]+=dp[i-1][m]
        else:
            dp[i][(m*10+int(S[i]))%13]+=dp[i-1][m]
    for m in range(13):
        dp[i][m]%=mod
#print(dp)
print(dp[-1][5]%mod)

Submission status: Accepted

Solution code:
def main():
    
    s = input()[::-1]
    mod = 10**9+7
    dp = [[0 for j in range(13)] for i in range(len(s)+1)]
    dp[0][0] = 1
    ten = 1


    for i in range(len(s)):
        if s[i] == "?":
            for k in range(10):
                x = k*ten%13
                for j in range(13):
                    dp[i+1][(j+x)%13] = (dp[i][j]+dp[i+1][(j+x)%13])%mod
        
        else:
            x = int(s[i])*ten%13
            for j in range(13):
                dp[i+1][(j+x)%13] = (dp[i][j]+dp[i+1][(j+x)%13])%mod

        ten = (ten*10)%13

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

if __name__ == "__main__":
    main()