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:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
 
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
 
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
 
def SMI(): return input().split()
def SLI(): return list(input())
 
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
 
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate
 
def solve():
    S = SLI()
    l = len(S)
    MOD = 1000000007
    dp = [[0]*13 for _ in range(l+1)]
    dp[0][0] = 1
    mul = 1
    S = S[::-1]
    for i in range(l):
        if S[i] == '?':
            for q in range(10):
                for j in range(13):
                    dp[i+1][(q*mul + j)%13] += dp[i][j]
                    dp[i+1][(q*mul + j)%13] %= MOD
        else:
            for j in range(13):
                k = int(S[i])
                dp[i+1][(k*mul + j)%13] += dp[i][j]
                dp[i+1][(k*mul + j)%13] %= MOD
 
        mul = mul * 10 % 13
    # print(dp[-1])
    print(dp[-1][5] % MOD)
 
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SMI(): return input().split()
def SLI(): return list(input())

def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')

# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    S = SLI()
    l = len(S)
    MOD = 1000000007
    dp = [[0]*13 for _ in range(l+1)]
    dp[0][0] = 1
    mul = 1
    S = S[::-1]
    for i in range(l):
        # s = S[-(i + 1)]
        # s = S[i]
        if S[i] == '?':
            for q in range(10):
                for j in range(13):
                    dp[i+1][(q*mul + j)%13] += dp[i][j]
                    dp[i+1][(q*mul + j)%13] %= MOD
        else:
            for j in range(13):
                k = int(S[i])
                dp[i+1][(k*mul + j)%13] += dp[i][j]
                dp[i+1][(k*mul + j)%13] %= MOD

        mul = mul * 10 % 13
    # print(dp[-1])
    print(dp[-1][5] % MOD)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SMI(): return input().split()
def SLI(): return list(input())

def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')

# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    S = SLI()
    l = len(S)
    MOD = 1000000007
    dp = [[0]*13 for _ in range(l+1)]
    dp[0][0] = 1
    mul = 1
    S = S[::-1]
    for i in range(l):
        # s = S[-(i + 1)]
        s = S[i]
        if s == '?':
            for q in range(10):
                for j in range(13):
                    dp[i+1][(q*mul + j)%13] += dp[i][j]
                    dp[i+1][(q*mul + j)%13] %= MOD
        else:
            for j in range(13):
                k = int(s)
                dp[i+1][(k*mul + j)%13] += dp[i][j]
                dp[i+1][(k*mul + j)%13] %= MOD

        mul = mul * 10 % 13
    # print(dp[-1])
    print(dp[-1][5] % MOD)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SMI(): return input().split()
def SLI(): return list(input())

def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')

# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    S = SLI()
    l = len(S)
    MOD = 1000000007
    dp = [[0]*13 for _ in range(l+1)]
    dp[0][0] = 1
    mul = 1
    R = S[::-1]
    for i in range(l):
        s = S[-(i + 1)]
        if s == '?':
            for q in range(10):
                for j in range(13):
                    dp[i+1][(q*mul + j)%13] += dp[i][j]
                    dp[i+1][(q*mul + j)%13] %= MOD
        else:
            for j in range(13):
                k = int(s)
                dp[i+1][(k*mul + j)%13] += dp[i][j]
                dp[i+1][(k*mul + j)%13] %= MOD

        mul = mul * 10 % 13
    # print(dp[-1])
    print(dp[-1][5] % MOD)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SMI(): return input().split()
def SLI(): return list(input())

def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')

# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    S = SLI()
    l = len(S)
    MOD = 1000000007
    dp = [[0]*13 for _ in range(l+1)]
    dp[0][0] = 1
    mul = 1
    for i in range(l):
        s = S[-(i + 1)]
        if s == '?':
            for q in range(10):
                for j in range(13):
                    dp[i+1][(q*mul + j)%13] += dp[i][j]
                    dp[i+1][(q*mul + j)%13] %= MOD
        else:
            for j in range(13):
                k = int(s)
                dp[i+1][(k*mul + j)%13] += dp[i][j]
                dp[i+1][(k*mul + j)%13] %= MOD

        mul = mul * 10 % 13
    # print(dp[-1])
    print(dp[-1][5] % MOD)

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

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

for i in range(len(S)):
    x = S[-(i + 1)]
    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])

Submission status: Accepted

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

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):
                dp[i+1][ (10*j+k)%13 ] += dp[i][j]
        else:
            k = int(S[i])
            dp[i+1][ (10*j+k)%13 ] += dp[i][j]
    for j in range(13):
        dp[i+1][j] %= MOD
print(dp[N][5])

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

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

s = input()
s = list(reversed(s))

mods = [0 for _ in range(13)]
mods[0] = 1

x = 1
MOD = 10 ** 9 + 7
for c in s:
    new_mods = [v for v in mods]
    val = 0
    if c == '?':
        for i in range(1, 10):
            val = i * x % 13
            for j in range(13):
                new_mods[j] += mods[j - val] % MOD
    else:
        val = int(c) * x % 13
        for i in range(13):
            new_mods[i] = mods[i - val] % MOD

    mods = new_mods
    # print(mods)
    x *= 10
    x %= 13
print(mods[5] % MOD)
# print(total_mod % 13)

Submission status: Accepted

Solution code:
class Mod13DPTable:
    MOD = 10**9 + 7
    def __init__(self, length):
        self.mod13 = [{j:0 for j in range(13)} for i in range(length)]
        self.MOD = 10**7 + 7
    def set_start(self, units_digit):
        if units_digit == '?':
            for i in range(10):
                self.mod13[0][i] = 1
        else:
            self.mod13[0][int(units_digit)] = 1
    def get_table(self, digit):
        return self.mod13[digit]
    def update(self, num, digit, multi):  # multi = 10**digit % 13
        for k, v in self.mod13[digit-1].items():
            remain = ((num * multi) + k) % 13
            self.mod13[digit][remain] = (self.mod13[digit][remain] + v) % Mod13DPTable.MOD
            
def main():
    MOD = 10**9 + 7
    S = input()
    mod13dp = Mod13DPTable(len(S))
    mod13dp.set_start(S[-1])
    multi = 10
    for i, m in enumerate(reversed(list(S[:-1]))):
        i += 1
        if m == '?':
            for j in range(10):
                mod13dp.update(j, i, multi)
        else:
            mod13dp.update(int(m), i, multi)
        multi = multi*10 % 13
    print(mod13dp.get_table(-1)[5])
main()

Submission status: Accepted

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

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

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

print(dp[n][5])

Submission status: Accepted

Solution code:
def main():
    s = input()
    mod = 13
    p = 10 ** 9 + 7
    dp = [0] * mod
    dp[0] = 1

    for i, ss in enumerate(s):
        tmp = [0] * mod
        if ss == "?":
            for j in range(10):
                for k in range(mod):
                    d = (10 * k + j) % mod
                    tmp[d] += dp[k]
                    tmp[d] %= p
        else:
            for k in range(mod):
                d = (10 * k + int(ss)) % mod
                tmp[d] += dp[k]
        dp = tmp
    print(dp[5])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    s = input()[::-1]
    mod = 13
    p = 10 ** 9 + 7
    dp = [0] * mod
    dp[0] = 1

    for i, ss in enumerate(s):
        tmp = [0] * mod
        if ss == "?":
            for j in range(10):
                d = j * pow(10, i, mod)
                for k in range(mod):
                    tmp[(k + d) % mod] += dp[k]
                    tmp[(k + d) % mod] %= p
        else:
            d = int(ss) * pow(10, i, mod)
            for k in range(mod):
                tmp[(k + d) % mod] += dp[k]
        dp = tmp
    print(dp[5])
if __name__ == '__main__':
    main()

Submission status: Accepted

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

    for i in range(len(s)):
        if s[i] == "?":
            for j in range(10):
                d = j * pow(10, i, mod)
                for k in range(13):
                    dp[i + 1][(k + d) % mod] += dp[i][k]
                    dp[i + 1][(k + d) % mod] %= p
        else:
            d = int(s[i]) * pow(10, i, mod)
            for k in range(13):
                dp[i + 1][(k + d) % mod] += dp[i][k]
    print(dp[-1][5])
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
s=list(input())
mod=10**9+7
n=len(s)
for i in range(n):
    if s[i]!="?":
        s[i]=int(s[i])
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):
                p=(k+10*j)%13
                dp[i+1][p]+=dp[i][j]
                dp[i+1][p]%=mod

    else:
        for j in range(13):
            p=(s[i]+10*j)%13
            dp[i+1][p]+=dp[i][j]
            dp[i+1][p]%=mod
print(dp[n][5])

Submission status: Accepted

Solution code:
from collections import defaultdict
s = input()[::-1]
mod = 13
p = 10 ** 9 + 7
dic = defaultdict(int)
dic[0] = 1

for i in range(len(s)):
    tmp = defaultdict(int)
    if s[i] == "?":
        for j in range(10):
            d = j * pow(10, i, mod)
            for k, v in dic.items():
                tmp[(k + d) % mod] += v
                tmp[(k + d) % mod] %= p
    else:
        d = int(s[i]) * pow(10, i, mod)
        for k, v in dic.items():
            tmp[(k + d) % mod] = v
    dic = tmp
print(dic[5] % p)

Submission status: Accepted

Solution code:
from collections import defaultdict
s = input()
lens = len(s)
"""
1, 10, 100～900に対して13で割って5余るものは存在する？
"""
modl = [[] for i in range(len(s))]
modl[0] = [i for i in range(10)]
for i in range(1, len(s)):
	modl[i] = [(modl[i-1][j]*10)%13 for j in range(10)]
mod = 10**9+7

unta = defaultdict(lambda: 0)
unta[0] += 1
for i, j in enumerate(s[::-1]):
	newunta = defaultdict(lambda: 0)
	if j != "?":
		a = modl[i][int(j)]
		for k in range(13):
			newunta[(k+a)%13] = (newunta[(k+a)%13] + unta[k]) % mod
	else:
		for l in range(10):
			a = modl[i][l]
			for k in range(13):
				newunta[(k+a)%13] = (newunta[(k+a)%13] + unta[k]) % mod
	unta = newunta

print(unta[5] % mod)

Submission status: Accepted

Solution code:
import collections
s = list(raw_input())
r = 0
mod = 10 ** 9 + 7
h= collections.Counter()
h[0] += 1
for v in s:

	v = int(v) if v != '?' else v
	hh = collections.Counter()
	for u in range(13):
		if v != '?':
			hh[(u * 10 + v) % 13] += h[u]

		else:
			for vv in range(10):
				hh[(u * 10 + vv) % 13] += h[u]
	for k in hh:
		hh[k] %= mod
	h = hh
print h[5]

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


def main():
    mod = 10 ** 9 + 7
    input = stdin.buffer.readline
    s = list(input()[:-1].decode())
    n = len(s)

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

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

    print(dp[5] % mod)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

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

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

for i, char in enumerate(s):
    dp_new = [0] * 13

    if char != '?':
        l = [int(char)]
    else:
        l = list(range(10))

    for k in l:
        tmp = pow(10, i, 13)
        tmp = (k * tmp) % 13

        for j in range(13):
            dp_new[(j + tmp) % 13] += dp[j]

    dp = []
    for x in dp_new:
        dp.append(x % mod)

print(dp[5])

Submission status: Accepted

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

    DP = [[0] * 13 for i in range(len(s) + 1)]
    DP[0][0] = 1
    for ci, c in enumerate(s):
        if c == '?':
            for r in range(13):
                for k in range(10):
                    DP[ci + 1][(r * 10 + k) % 13] += DP[ci][r]
                    DP[ci + 1][(r * 10 + k) % 13] %= mod

        else:
            for r in range(13):
                DP[ci + 1][(r * 10 + int(c)) % 13] += DP[ci][r]
                DP[ci + 1][(r * 10 + int(c)) % 13] %= mod

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
  s=list(input())
  n=len(s)
  dp=[0]*13
  mod=pow(10,9)+7
  if s[-1]=='?':
    dp=[1]*10+[0]*3
  else:
    dp[int(s[-1])]=1
  p_dp=[0]*13
  for i in range(2,n+1):
    if s[-i]=='?':
      for j in range(10):
        a=(j*pow(10,i-1,13))%13
        for k in range(13):
          p_dp[(a+k)%13]+=dp[k]
    else:
      j=int(s[-i])
      a=(j*pow(10,i-1,13))%13
      for k in range(13):
        p_dp[(a+k)%13]+=dp[k]
    
    for k in range(13):
      p_dp[k]%=mod
    dp=[k for k in p_dp]
    p_dp=[0]*13
  print(dp[5])

if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())

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] == '?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(s[-1])] = 1

digits = 1
for i in range(1, len_s):
    digits = (digits * 10)%13
    for j in range(13):

        if dp[i - 1][j] > 0:
            if s[-(i + 1)] != '?':
                add = int(s[-(i + 1)]) * digits
                dp[i][(j + add)%13] = (dp[i][(j + add)%13] + dp[i - 1][j])%mod
            else:
                for k in range(10):
                    # k:先頭に加える数字
                    add = k * digits
                    dp[i][(j + add) % 13] = (dp[i][(j + add) % 13] + dp[i - 1][j]) % mod

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

Submission status: Accepted

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

  mul = (mul * 10) % 13
    
print(dp[len(S)][5]%mod)

Submission status: Accepted

Solution code:
def main():
    s = input()
    mod = 10 ** 9 + 7
    table1 = [0] * 13
    table2 = [0] * 13
    table1[0] = 1
    pre = [[((10 * i + j) % 13) for j in range(10)] for i in range(13)]

    for l in s:
        for i in range(13):
            q = table1[i] % mod
            if q == 0:
                continue
            if l == '?':
                for k in pre[i]:
                    table2[k] += q
            else:
                k = (10 * i + int(l)) % 13
                table2[k] += q

        table1 = table2
        table2 = [0] * 13

    print(table1[5] % mod)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

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

Submission status: Accepted

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

for i, s in enumerate(S):
    if s != '?':
        a = int(s) * pow(10, i, 13) % 13
        for j in range(13):
            DP[i+1][j] += DP[i][(j-a) % 13] % mod

    else:
        for k in range(10):
            a = k * pow(10, i, 13) % 13
            for j in range(13):
                DP[i + 1][j] += DP[i][(j - a) % 13] % mod

print(DP[N][5] % mod)

Submission status: Accepted

Solution code:
# PyPy3 (2.4.0)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
S = input().rstrip()
mod = 10**9+7

# dp[i][j] : 上から i 桁までの数字で, 13で割ったあまりが j になる場合の数
dp = [[0 for _ in range(13)] for _ in range(len(S))]

# 初期化
if S[0] == "?":
    for i in range(10):
        dp[0][i] += 1
else:
    dp[0][int(S[0])] = 1

# dp更新
for i in range(1,len(S)):
    if S[i] == "?":
        for j in range(13):
            for k in range(10):
                dp[i][(j*10 + k) % 13] += dp[i-1][j]
                dp[i][(j*10 + k) % 13] %= mod
    else:
        for j in range(13):
            dp[i][(j*10 + int(S[i])) % 13] += dp[i-1][j]
            dp[i][(j*10 + int(S[i])) % 13] %= mod

print(dp[-1][5])

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import fractions
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

S = input()
N = len(S)
modlist = [0] * 13
splitmod = []

if S[0] == "?":
    for i in range(10):
        modlist[i % 13] += 1
else:
    modlist[int(S[0])] += 1
S = S[1:]

# 前から処理していく
# 10と13は互いに素なので
# a == b (mod z)なら
# 10a == 10b (mod z)
# 例
# 18 == 5 (mod 13)
# 180 == 50 (mod 13)
# 13 * 13 + 11 == 13 * 3 + 11 (mod 13)
for st in S:
    modalta = [0] * 13
    if st == "?":
        # 例えば 7?4の時
        # 7 * 10 + 1, 2, 3...
        for i in range(10):
            # modlist
            for j in range(13):
                opt = (j * 10 + i) % 13
                modalta[opt] += modlist[j]
    else:
        for j in range(13):
            opt = (j * 10 + int(st)) % 13
            modalta[opt] += modlist[j]
    # mod調整
    for i in range(13):
        modalta[i] %= mod
    modlist = copy.deepcopy(modalta)

print(modlist[5] % mod)

Submission status: Accepted

Solution code:
S = input()[::-1]
keta = len(S)
mod = 10 ** 9 + 7

dp = [[0 for _ in range(13)] for _ in range(keta + 1)]
dp[0][0] = 1
tmp = 1
for i in range(1, keta + 1):
    if S[i - 1] != "?":
        x = int(S[i - 1]) * (tmp) % 13
        for j in range(13):
            dp[i][(x + j) % 13] += dp[i - 1][j] % mod
    else:
        for k in range(10):
            x = k * (tmp) % 13
            for j in range(13):
                dp[i][(x + j) % 13] += dp[i - 1][j] % mod
    tmp *= 10
    tmp %= 13

print(dp[keta][5] % mod)

Submission status: Accepted

Solution code:
s = input().rstrip()

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

rev = [0] * 13
for i, ni in enumerate(n):
    rev[ni] = i

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

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

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

print(dp[-1][5])

Submission status: Accepted

Solution code:
s = input()
keta = len(s)
mod = 10 ** 9 + 7
dp = [[0] * (13) for _ in range(keta + 1)]
dp[0][0] = 1
for i in range(keta):
    if s[i] == "?":
        num = -1
    else:
        num = int(s[i])
    ni = i + 1
    juu = pow(10, keta - 1 - i, 13)
    for j in range(13):
        nj = j
        if num == -1:
            for d in range(10):
                nj = j + d * juu
                nj %= 13
                dp[ni][nj] += dp[i][j]
                dp[ni][nj] %= mod
                continue
        else:
            nj = j + num * juu
            nj %= 13
            dp[ni][nj] += dp[i][j]
            dp[ni][nj] %= mod
print(dp[keta][5])

Submission status: Accepted

Solution code:
s = input()

dp = [[0 for i in range(13)] for j in range(len(s)+1)]
dp[0][0]=1
keta = 1
di=10**9+7
ii = len(s)
for i in range(len(s)):
    if s[ii-1-i] != "?":
        for j in range(13):
            dp[i+1][(keta*int(s[ii-1-i])+j)%13]=(dp[i+1][(keta*int(s[ii-1-i])+j)%13]+dp[i][j])%di
    else:
        for j in range(13):
            for num in range(10):
                #print(dp[i][j])
                dp[i+1][(keta*num+j)%13]=(dp[i+1][(keta*num+j)%13]+dp[i][j])%di
    keta = (keta*10)%13

#print(*dp,sep="\n")
print(dp[len(s)][5])

Submission status: Accepted

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

base = 1
for i in range(N):
    if S[N-1-i] != '?':
        mi = int(S[N-1-i])*base
        mi %= 13
        for j in range(13):
            dp[i+1][(j+mi)%13] += dp[i][j]
            dp[i+1][(j+mi)%13] %= MOD
    else:
        for j in range(13):
            for k in range(10):
                Ti = base * k
                Ti %= 13
                dp[i+1][(j+Ti)%13] += dp[i][j]
                dp[i+1][(j+Ti)%13] %= MOD
    base *= 10
    base %= 13
print(dp[N][5])

Submission status: Accepted

Solution code:
# 解説を参考に作成
# #11254823を参考


def solve():
    S = input()
    mod = 10 ** 9 + 7

    '''
    桁数毎・余りの数字ごとのdpを作成するにあたり、mapを作る.
    たとえば新しい数字Yは前の数字Xの右側に新たに桁を作って
        Y = X(前の数字) * 10 + i(0 <= i <= 9)
    と表せる.
    この Y の余りは、
        Y % 13 = ((X % 13) * 10 + i) % 13
    と表せるので、10 * 13 のマップであらかじめ計算しておくことができる.
    このマップを以下で作っている.
        modmap[新しい桁の数字i][新しい余り(Y % 13 = k)] = 前の数字の時の余り(X % 13 = j)
    '''
    modmap = []
    for i in range(10):
        modmap.append([0] * 13)
        for j in range(13):
            k = (j * 10 + i) % 13
            modmap[i][k] = j

    # なぜ最初を1にするのか？
    # → Sの先頭に 0 を固定でつけても結果は変化しない. また付けた場合の最初の計算では余り0となる.
    # → どんなパターンでも共通の初期状態として使用できる.
    dp = [1] + [0] * 12
    for s in S:
        if s == '?':
            dp = [sum(dp[l] for l in modlist) % mod for modlist in zip(*modmap)]
        else:
            modlist = modmap[int(s)]
            dp = [dp[modlist[l]] % mod for l in range(13)]

    print(dp[5])


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
s=input()

#i桁以下の数字でmodがjの数
#dp[i][j]=

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

MOD=10**9+7

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


for i in range(1,len(s)):
    si=s[i]


    if s[i]!="?":
        #数字,300のmodをtempに
        for j in range(13):
            dp[i][(j*10+int(si))%13]+=dp[i-1][j]%MOD
    else:
        for l in range(10):
            for j in range(13):
                dp[i][(j*10+l)%13]+=dp[i-1][j]%MOD
    #print(dp[i],sum(dp[i]))



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