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

S = input().strip()
#S = '?' * (10 ** 5)
N = 13

dp = [0] * N
dp[0] = 1

for i in range(len(S)):
  next_dp = [0] * N
  c = S[i]
  if c == '?':
    for k in range(10):
      for j in range(N):
        next_dp[(j * 10 + k) % N] += dp[j]
        next_dp[(j * 10 + k) % N] %= MOD
  else:
    k = int(c)
    for j in range(N):
      next_dp[(j * 10 + k) % N] += dp[j]
      next_dp[(j * 10 + k) % N] %= MOD

  dp = next_dp

print(dp[5])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
S = input()
S = S[::-1]
#print(S)

mod = 10**9+7

table = [1,10,9,12,3,4]
#for i in range(1,len(S)+1):
#	tblpow.append(10*tblpow[i-1]%13)

dp = [0]*13
dp[0] = 1
for i in range(len(S)-1,-1,-1):
	ch = int(S[i]) if S[i]!='?' else -1
	temp = [0]*13
	for d in range(10):
		if ch!=-1 and ch!=d:
			continue
		for m in range(13):
			temp[(d*table[i%6]+m)%13] += dp[m]
	for m in range(13):
		temp[m] %= mod
	dp = temp
print(dp[5])

Submission status: Accepted

Solution code:
S = input()
S = S[::-1]
#print(S)

mod = 10**9+7

tblpow = [1]
for i in range(1,len(S)+1):
	tblpow.append(10*tblpow[i-1]%13)

dp = [0]*13
dp[0] = 1
for i in range(len(S)-1,-1,-1):
	ch = int(S[i]) if S[i]!='?' else -1
	temp = [0]*13
	for d in range(10):
		if ch!=-1 and ch!=d:
			continue
		for m in range(13):
			temp[(d*tblpow[i]+m)%13] += dp[m]
	for m in range(13):
		temp[m] %= mod
	dp = temp
print(dp[5])

Submission status: Accepted

Solution code:
import copy

s = input()
dp = [0 for i in range(13)]
dp[0] = 1
num = 0
c = 1000000007
mul = 1
for i in range(len(s) - 1, -1, -1):
    nextdp = [0 for i in range(13)]
    if s[i] == '?':
        for j in range(10):
            for k in range(13):
                nextdp[(j * mul + k) % 13] += dp[k]
                nextdp[(j * mul + k) % 13] %= c
    else:
        j = int(s[i])
        for k in range(13):
            nextdp[(j * mul + k) % 13] += dp[k]
            nextdp[(j * mul + k) % 13] %= c
    dp = copy.copy(nextdp)
    mul *= 10
    mul %= 13

print(dp[5])

Submission status: Accepted

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

import sys

sys.setrecursionlimit(10**7)

# Override `input` function because `stdin.readline()` is 10x faster than built-in `input()`
input = sys.stdin.readline


def read_h(typ=int):
    return list(map(typ, input().split()))


def read_v(n, m=1, typ=int):
    return [read_h(typ) if m > 1 else typ(input()) for _ in range(n)]


def main():
    S, = read_h(typ=str)
    n = len(S)

    MOD = 10**9 + 7

    dp = [[0] * 13 for _ in range(10**5 + 2)]
    dp[0][0] = 1
    #  print('initial dp:', dp)

    for i, s in enumerate(S):
        c = -1 if s == '?' else ord(s) - ord('0')
        #  print('c:', c)

        for j in range(10):
            if c != -1 and c != j:
                continue

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

            #  print('updated dp:', dp[:])

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

        #  print('final dp:', dp[:])

    res = dp[n][5]
    print(res)


if __name__ == '__main__':
    main()

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)
    t = [0] * 13
    t[0] = 1
    m = 1
    for i, c in enumerate(reversed(S)):
        if c != '?':
            n = (m * int(c)) % 13
            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 = (m * j) % 13
                for k in range(13):
                    nt[(k+n) % 13] = M.add(nt[(k+n) % 13], t[k])
            t = nt
        m *= 10
        m %= 13
    return t[5]


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S = input()[::-1]
L = len(S)

mod = [0] * (L+1)
mod[0] = 1
for i in range(1, L+1):
  mod[i] = (mod[i-1] * 10) % 13
MOD = 10 ** 9 + 7

dp = [[0]*13 for i in range(L)]
flag = True

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

for i in range(1, L):
  if S[i] == '?':
    for j in range(10):
      m = (j * mod[i]) % 13
      for k in range(13):
          dp[i][(m+k)%13] += dp[i-1][k]      
  else:
    m = (int(S[i]) * mod[i]) % 13
    for k in range(13):
       dp[i][(m+k)%13] = dp[i-1][k]
        
  for j in range(13):
    dp[i][j] = dp[i][j] % MOD

print(dp[-1][5])

Submission status: Accepted

Solution code:
import sys
import numpy as np

MOD = 1000000007
S = np.frombuffer(sys.stdin.buffer.read(), dtype=np.int8)
S = S[:-1][::-1] - 48

a = 10 ** np.arange(6) % 13
b = np.tile(np.arange(10), (6, 1))
c = a * b.T % 13
c = c.T
f = np.zeros((6, 13, 13), dtype=np.int64)
for i in range(6):
    f[i, 0, c[i]] = 1
    for j in range(12):
        f[i, j + 1] = np.roll(f[i, j], 1)

dp = np.zeros(13, dtype=np.int64)
dp[0] = 1
digit = 0
count = 0

for i, c in enumerate(S):
    k = i % 6
    if c == 15:
        dp = np.dot(dp, f[k]) % MOD
    else:
        digit += a[k] * c

m = (5 - digit) % 13
print(dp[m])

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

S = input()

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

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

Submission status: Accepted

Solution code:
S = input()

MOD = 10 ** 9 + 7

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

Submission status: Accepted

Solution code:
from sys import stdin

def main():
    s = [int(x) if x != "?" else "?" for x in stdin.readline().rstrip()]

    dp = [1] + [0]*12
    mod = 10 ** 9 + 7
    mul = 1
    s.reverse()

    for i in (range(0,len(s))):
        next_dp = [0]*13
        if s[i] == "?":
            for k in range(0, 10):
                for j in range(0, 13):
                    next_dp[(k*mul+j)%13] += dp[j]
                    next_dp[(k*mul+j)%13] %= mod

        else:
            k = s[i]
            for j in range(0, 13):
                    next_dp[(k*mul+j)%13] += dp[j]
                    next_dp[(k*mul+j)%13] %= mod

        mul = mul * 10 % 13
        dp = next_dp

    print(dp[5])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = int(1e9 + 7)
N = int(1e5)
M = 13

s = input()
dp = [[0 for x in range(M)] for x in range(N+10)]
dp[0][0] = 1

for i in range(len(s)):
    for j in range(M):
        for k in range(10):
            if s[i] == "?" or s[i] == str(k):
                dp[i+1][(j*10 +k) % M] += dp[i][j]
                dp[i+1][(j*10 +k) % M] %= MOD


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

Submission status: Accepted

Solution code:
d={i:0 for i in range(13)}
d[0]=1
s=input()
for k,t in enumerate(s[::-1]):
    if t=='?':
        d2={i:0 for i in range(13)}
        for i in range(10):
            u=i*pow(10,k,13)
            for i in range(13):
                d2[(i+u)%13]+=d[i]
    else:
        u=int(t)*pow(10,k,13)
        d2={i:0 for i in range(13)}
        for i in range(13):
            d2[(i+u)%13]+=d[i]
    for i in range(13):
        d[i]=d2[i]%(10**9+7)
print(d[5])

Submission status: Accepted

Solution code:
d=[0]*13
d[0]=1
s=input()
for k,t in enumerate(s[::-1]):
    if t=='?':
        d2=[0]*13
        for i in range(10):
            u=i*pow(10,k,13)
            for i in range(13):
                d2[(i+u)%13]+=d[i]
    else:
        u=int(t)*pow(10,k,13)
        d2=[0]*13
        for i in range(13):
            d2[(i+u)%13]+=d[i]
    for i in range(13):
        d[i]=d2[i]%(10**9+7)
print(d[5])

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

s = input()

cur = [0] * 13
cur[0] = 1
d = 1
for c in s[::-1]:
    if c != '?':
        l = [int(c)]
    else:
        l = [j for j in range(10)]
    tmp = [0] * 13
    for j in l:
        for k in range(13):
            ind = (j * d + k) % 13
            tmp[ind] += cur[k]
            tmp[ind] %= mod
    cur = tmp
    d *= 10
    d %= 13
print(cur[5])

Submission status: Accepted

Solution code:
import numpy as np

MOD = 1000000007
S = input()[::-1]

a = 10 ** np.arange(6) % 13
b = np.tile(np.arange(10),(6, 1))
c = a * b.T % 13
c = c.T
f = np.zeros((6, 13, 13), dtype=np.int64)
for i in range(6):
    f[i, 0, c[i]] = 1
    for j in range(12):
        f[i, j + 1] = np.roll(f[i, j], 1)

prev = np.zeros(13, dtype=np.int64)
prev[0] = 1
digit = 0

for i, c in enumerate(S):
    k = i % 6
    if c == '?':
        cur = np.dot(prev, f[k]) % MOD
        prev, cur = cur, prev
    else:
        digit += a[k] * (ord(c) - ord('0'))

m = (5 - digit) % 13
print(prev[m])

Submission status: Accepted

Solution code:
def main():
  s = ''.join(reversed(input()))
  multiplier = 1
  divisor = 10 ** 9 + 7
  list10 = list(range(10))
  list13 = list(range(13))
  p = [0] * 13
  np = [0] * 13
  rt = [i % 13 for i in range(121)]
  p[0] = 1
  for i in range(len(s)):
    if s[i] != '?':
      r = rt[int(s[i]) * multiplier]
      for j in list13:
        np[rt[j + r]] = p[j]
    else:
      r = 0
      for j in list10:
        for k in list13:
          np[rt[k + r]] += p[k]
        r = rt[r + multiplier]
    for j in list13:
      p[j] = np[j] % divisor
      np[j] = 0
    multiplier = rt[10 * multiplier]
  print(p[5])
main()

Submission status: Accepted

Solution code:
def resolve():

    s = input()
    n = len(s)

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

    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 k in range(13):
                dp[i+1][(k*10+j) % 13] += dp[i][k]
        for j in range(13):
            dp[i+1][j] %= 1000000007

    print(dp[n][5])
    
resolve()

Submission status: Accepted

Solution code:
M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for c in reversed(input()):
    r = [x % 13 for x in range(0, p * 10, p)] if c == '?' else (p * int(c) % 13,)
    a = [sum(a[(i - j, i - j + 13)[i < j]] for j in r) % M for i in range(13)]
    p = p * 10 % 13
print(a[5])

Submission status: Accepted

Solution code:
def resolve():
    ss = input()

    dp = [0] * 13
    dp[0] = 1

    mod = 10 ** 9 + 7
    mul = 1

    # 後ろから解く
    for s in ss[::-1]:
        next_dp = [0] * 13

        if s == '?':
            for num in range(10):
                for i in range(13):
                    next_dp[(num * mul + i) % 13] += dp[i]
                    next_dp[(num * mul + i) % 13] %= mod
        else:
            num = int(s)
            for i in range(13):
                next_dp[(num * mul + i) % 13] += dp[i]
                next_dp[(num * mul + i) % 13] %= mod

        mul *= 10
        mul %= 13
        dp = next_dp

    print(dp[5])
    
resolve()

Submission status: Accepted

Solution code:
# -*- coding utf-8 -*-
MOD = 10 ** 9 + 7

S = input()
# S = '?' * 100000
mods = [0] * 13
mods[0] = 1

digit = 1
for s in S[::-1]:
    next_mods = [0] * 13
    if s == '?':
        for i in range(10):
            for m in range(13):
                next_mods[(m + i * digit) % 13] += mods[m]
    else:
        for m in range(13):
            next_mods[(m + int(s) * digit) % 13] += mods[m]

    for m in range(13):
        next_mods[m] %= MOD
    mods = next_mods
    digit *= 10
    digit %= 13    # this line dramatically reduces calculation time

ans = mods[5]

print(ans)

Submission status: Accepted

Solution code:
M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for c in reversed(input()):
    r = range(0, p * 10, p) if c == '?' else (p * int(c),)
    a = [sum(a[(i - j) % 13] for j in r) % M for i in range(13)]
    p = p * 10 % 13
print(a[5])

Submission status: Accepted

Solution code:
M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for c in reversed(input()):
    if c == '?':
        b = a[:]
        for j in range(-p, -p * 10, -p):
            j %= 13
            a = [sum(x) % M for x in zip(a, b[j:] + b[:j])]
    elif c > '0':
        j = -p * int(c) % 13
        a = a[j:] + a[:j]
    p = p * 10 % 13
print(a[5])

Submission status: Accepted

Solution code:
s = input()

mod = 1000000007
n = 13

dp = [0] * 13
dp[0] = 1

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

    mul *= 10
    mul %= n
    dp = nextDp
print(dp[5])

Submission status: Accepted

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

def main():
	mod = 10**9 + 7
	N = 13
	dp = [0] * N
	dp[0] = 1
	s = input().strip()
	mul = 1
	for i in reversed(range(len(s))):
		# print(dp)
		nextdp = [0] * N
		if s[i] == '?':
			for k in range(10):
				for j in range(N):
					nextdp[(k * mul + j) % N] += dp[j]
					nextdp[(k * mul + j) % N] %= mod
		else:
			k = int(s[i])
			# print("c: {},{}".format(i, k))
			for j in range(N):
				nextdp[(k * mul + j) % N] += dp[j]
				nextdp[(k * mul + j) % N] %= mod
		mul *= 10
		mul %= N
		dp = nextdp
	# print(dp)
	print(dp[5])

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for c in input()[::-1]:
    r = range(0, p * 10, p) if c == '?' else (p * int(c),)
    a = [sum(a[(i - j) % 13] for j in r) % M for i in range(13)]
    p = p * 10 % 13
print(a[5])

Submission status: Accepted

Solution code:
M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for k, c in enumerate(reversed(input())):
    r = range(0, p * 10, p) if c == '?' else (p * int(c),)
    a = [sum(a[(i - j) % 13] for j in r) % M for i in range(13)]
    p = p * 10 % 13
print(a[5])

Submission status: Accepted

Solution code:
M = 10**9 + 7
a = [1] + [0] * 12
b = 1, 10, 9, 12, 3, 4
for k, c in enumerate(reversed(input())):
    p = b[k % 6]
    r = range(0, p * 10, p) if c == '?' else (p * int(c),)
    a = [sum(a[(i - j) % 13] for j in r) % M for i in range(13)]
print(a[5])

Submission status: Accepted

Solution code:
M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for c in reversed(input()):
    if c > '0':
        r = range(0, p * 10, p) if c == '?' else (p * int(c),)
        a = [sum(a[(i - j) % 13] for j in r) % M for i in range(13)]
    p = p * 10 % 13
print(a[5])

Submission status: Accepted

Solution code:
s = list(str(input()))

n = len(s)
dp = [0] * 13
dp[0] = 1

for i in range(n):
    prev = dp[:]
    dp = [0]*13

    if s[i] == '?':
        for z in range(10):
            for j in range(13):
                dp[(j*10+z)%13] += prev[j]
                dp[(j*10+z)%13] %= 10**9+7

    else:
       _s = int(s[i])
       for j in range(13):
            dp[(j*10+_s)%13] += prev[j]
            dp[(j*10+_s)%13] %= 10**9+7

print(dp[5])

Submission status: Accepted

Solution code:
M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for c in reversed(input()):
    if c == '?':
        a = [sum(x) % M for x in zip(*(a[j % 13:] + a[:j % 13]
                              for j in range(0, -p * 10, -p)))]
    elif c > '0':
        j = -p * int(c) % 13
        a = a[j:] + a[:j]
    p = p * 10 % 13
print(a[5])

Submission status: Accepted

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

T = [s if s != "?" else "0" for s in S]
T = int(''.join(T))
SS = T % 13

def get_mod(S):
    c = {}
    iii = 1
    for i in range(len(S)):
        if S[len(S) - i - 1] != "?":
            iii *= 10
            iii %= 13
            continue
        c[i] = {(j * iii) % 13: 1 for j in range(0, 10)}
        iii *= 10
        iii %= 13
    return c
c = get_mod(S)

def get_tdp(pdp):
    tdp = {i: 0 for i in range(13)}
    for r in v.keys():
        for _r, _v in pdp.items():
            tdp[(_r + r) % 13] += _v
    for i in range(13):
        tdp[i] %= con
    return tdp

pdp = {i: 0 for i in range(13)}
pdp[SS] += 1
for k, v in c.items():
    pdp = get_tdp(pdp)

ans = pdp[5]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
S = input()
N = len(S)
dp = [[0 for i in range(13)] for j in range(N+1)]

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

print(dp[N][5])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
S = [int(x) if x != "?" else -1 for x in input()]
g = 10 ** 9 + 7
x = 1
DP = [[0] * 13 for _ in range(2)]
DP[0][0] = 1
for i in range(len(S)):
    for j in range(13):
        DP[1][j] = DP[0][j] % g
        DP[0][j] = 0
    for j in range(13):
        if S[i] == -1:
            s = (j*10)%13
            e = (s+10)%13
        else:
            s = (j*10+S[i])%13
            e = (s+1)%13
        DP[0][s] += DP[1][j]
        if s > e:
            DP[0][0] += DP[1][j]
        DP[0][e] -= DP[1][j]
    w = 0
    for j in range(13):
        w += DP[0][j]
        DP[0][j] = w

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

Submission status: Accepted

Solution code:
INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
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] %= INF
    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] %= INF
    mul = mul * 10 % 13

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

Submission status: Accepted

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

cur = [0] * 13
cur[0] = 1
r = 1
base = 0
for i in range(len(S)):
    s = S[-(i+1)]
    if s == '?':
        prev = cur
        cur = [sum(prev)] * 13
        for m in range(13):
            for d in range(10,13):
                cur[(m + r*d) % 13] -= prev[m]
        for m in range(13):
            cur[m] %= MOD
    else:
        base = (base + r*int(s)) % 13

    r = (10 * r) % 13

print(cur[(5-base) % 13])

Submission status: Accepted

Solution code:
def main():
  s = ''.join(reversed(input()))
  multiplier = 1
  divisor = 10 ** 9 + 7
  list10 = list(range(10))
  list13 = list(range(13))
  p = [0 for i in list13]
  np = [0 for i in list13]
  rt = [i % 13 for i in range(100)]
  if s[0] != '?':
    p[int(s[0])] = 1
  else:
    for j in range(10):
      p[j] = 1
  for i in range(1, len(s)):
    multiplier = (10 * multiplier) % 13
    if s[i] != '?':
      r = int(s[i]) * multiplier
      for j in list13:
        np[(j + r) % 13] = p[j]
    else:
      for j in range(10):
        r = multiplier * j % 13
        for k in list13:
          np[rt[k + r]] += p[k]
    for j in list13:
      p[j] = np[j] % divisor
      np[j] = 0
  print(p[5] % divisor)
main()

Submission status: Accepted

Solution code:
S = input()

MOD=(10**9) + 7
N=13

dp=[[0 for i in range(N)] for j in range(100005)]
dp[0][0] = 1

dpi = 1
mul = 1

for c in S[::-1]:    
    for i in range(N):
        if c=='?':
            for j in range(10):
                ii = (i + (j*mul)) % N
                dp[dpi][ii] += dp[dpi-1][i] % MOD
                #pass
        else:
            j = int(c)
            ii = (i + (j*mul)) % N
            dp[dpi][ii] += dp[dpi-1][i] % MOD
            #pass
    mul *= 10
    mul %= N
    dpi += 1

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

Submission status: Accepted

Solution code:
modarr61=[76924, 76923, 76923, 76923, 76923, 76923, 76923, 76923, 76923, 76923, 76923, 76923, 76923]
modarr51=[7693, 7692, 7692, 7692, 7693, 7692, 7692, 7693, 7692, 7692, 7693, 7692, 7692]
modarr52=[7693, 7693, 7692, 7692, 7692, 7693, 7692, 7692, 7692, 7693, 7692, 7692, 7692]
modarr53=[7693, 7692, 7692, 7692, 7692, 7692, 7692, 7692, 7692, 7692, 7693, 7693, 7693]
modarr54=[7693, 7692, 7692, 7693, 7692, 7692, 7693, 7692, 7692, 7693, 7692, 7692, 7692]
modarr55=[7693, 7692, 7692, 7692, 7693, 7692, 7692, 7692, 7693, 7692, 7692, 7692, 7693]
modarr56=[7693, 7693, 7693, 7693, 7692, 7692, 7692, 7692, 7692, 7692, 7692, 7692, 7692]
modarr41=[770, 769, 769, 769, 769, 770, 769, 769, 769, 770, 769, 769, 769]
modarr42=[769, 769, 769, 769, 770, 769, 769, 770, 769, 769, 770, 769, 769]
modarr43=[770, 769, 769, 769, 769, 769, 769, 769, 769, 769, 769, 770, 770]
modarr44=[772, 768, 768, 771, 769, 768, 770, 770, 768, 769, 771, 768, 768]
modarr45=[769, 770, 769, 769, 769, 770, 769, 769, 769, 770, 769, 769, 769]
modarr46=[770, 769, 769, 770, 769, 769, 770, 769, 769, 769, 769, 769, 769]
modarr47=[769, 769, 769, 769, 770, 769, 769, 769, 770, 769, 769, 769, 770]
modarr48=[772, 769, 768, 768, 771, 770, 768, 768, 770, 771, 768, 768, 769]
modarr49=[769, 769, 769, 769, 769, 769, 769, 769, 769, 769, 770, 770, 770]
modarr410=[770, 769, 769, 769, 770, 769, 769, 769, 770, 769, 769, 769, 769]
modarr411=[770, 769, 769, 769, 769, 769, 769, 770, 769, 769, 770, 769, 769]
modarr412=[769, 770, 770, 770, 769, 769, 769, 769, 769, 769, 769, 769, 769]
modarr413=[772, 771, 770, 769, 768, 768, 768, 768, 768, 768, 769, 770, 771]
modarr414=[769, 769, 769, 770, 769, 769, 770, 769, 769, 770, 769, 769, 769]
modarr415=[770, 770, 770, 769, 769, 769, 769, 769, 769, 769, 769, 769, 769]
modarr31=[77, 76, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77]
modarr32=[77, 77, 77, 77, 76, 78, 77, 76, 77, 78, 76, 77, 77]
modarr33=[79, 76, 76, 78, 77, 76, 77, 78, 76, 76, 79, 76, 76]
modarr34=[77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 76, 77, 77]
modarr35=[79, 76, 76, 76, 79, 77, 76, 76, 78, 78, 76, 76, 77]
modarr36=[76, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77]
modarr37=[77, 76, 77, 77, 77, 76, 77, 77, 77, 76, 77, 78, 78]
modarr38=[77, 77, 77, 76, 78, 77, 76, 77, 78, 76, 77, 77, 77]
modarr39=[79, 77, 76, 76, 78, 78, 76, 76, 77, 79, 76, 76, 76]
modarr310=[77, 77, 77, 77, 77, 77, 77, 77, 77, 76, 77, 77, 77]
modarr311=[77, 77, 77, 77, 76, 77, 77, 77, 77, 77, 77, 77, 77]
modarr312=[77, 76, 76, 76, 77, 77, 77, 78, 77, 77, 78, 77, 77]
modarr313=[79, 79, 78, 77, 76, 76, 76, 76, 76, 76, 76, 77, 78]
modarr314=[79, 76, 76, 79, 76, 76, 78, 77, 76, 77, 78, 76, 76]
modarr315=[76, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77]
modarr316=[77, 77, 77, 78, 77, 77, 78, 77, 77, 77, 76, 76, 76]
modarr317=[77, 77, 77, 76, 77, 77, 77, 77, 77, 77, 77, 77, 77]
modarr318=[77, 78, 78, 77, 76, 77, 77, 77, 76, 77, 77, 77, 76]
modarr319=[79, 78, 77, 76, 76, 76, 76, 76, 76, 76, 77, 78, 79]
modarr320=[77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 76]
modarr21=[8, 7, 8, 8, 7, 8, 8, 7, 8, 8, 7, 8, 8]
modarr22=[7, 7, 8, 8, 8, 7, 8, 8, 8, 7, 8, 8, 8]
modarr23=[10, 7, 7, 7, 9, 8, 7, 7, 8, 9, 7, 7, 7]
modarr24=[7, 8, 8, 7, 8, 8, 7, 8, 8, 7, 8, 8, 8]
modarr25=[8, 7, 8, 8, 8, 7, 8, 8, 8, 7, 7, 8, 8]
modarr26=[8, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8]
modarr27=[7, 8, 8, 8, 7, 8, 8, 7, 8, 8, 7, 8, 8]
modarr28=[10, 7, 7, 9, 7, 7, 8, 8, 7, 7, 9, 7, 7]
modarr29=[7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 7, 7, 7]
modarr210=[8, 8, 8, 7, 7, 8, 8, 8, 7, 8, 8, 8, 7]
modarr211=[7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8]
modarr212=[10, 9, 8, 7, 7, 7, 7, 7, 7, 7, 7, 8, 9]
modarr213=[8, 8, 8, 7, 8, 8, 7, 8, 8, 7, 8, 8, 7]
modarr214=[7, 8, 8, 8, 7, 8, 8, 8, 7, 8, 8, 8, 7]
modarr215=[8, 8, 8, 8, 8, 8, 8, 8, 8, 7, 7, 7, 7]
modarr11=[1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1]
modarr12=[1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1]
modarr13=[1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
modarr14=[1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0]
modarr15=[1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1]
modarr16=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0]

def makemod(n):
  if n==100000:
    return modarr11
  elif n==10000:
    return modarr12
  elif n==1000:
    return modarr13
  elif n==100:
    return modarr14
  elif n==10:
    return modarr15
  elif n==1:
    return modarr16
  elif n==110000:
    return modarr21
  elif n==101000:
    return modarr22
  elif n==100100:
    return modarr23
  elif n==100010:
    return modarr24
  elif n==100001:
    return modarr25
  elif n==11000:
    return modarr26
  elif n==10100:
    return modarr27
  elif n==10010:
    return modarr28
  elif n==10001:
    return modarr29
  elif n==1100:
    return modarr210
  elif n==1010:
    return modarr211
  elif n==1001:
    return modarr212
  elif n==110:
    return modarr213
  elif n==101:
    return modarr214
  elif n==11:
    return modarr215
  elif n==111000:
    return modarr31
  elif n==110100:
    return modarr32
  elif n==110010:
    return modarr33
  elif n==110001:
    return modarr34
  elif n==101100:
    return modarr35
  elif n==101010:
    return modarr36
  elif n==101001:
    return modarr37
  elif n==100110:
    return modarr38
  elif n==100101:
    return modarr39
  elif n==100011:
    return modarr310
  elif n==11100:
    return modarr311
  elif n==11010:
    return modarr312
  elif n==11001:
    return modarr313
  elif n==10110:
    return modarr314
  elif n==10101:
    return modarr315
  elif n==10011:
    return modarr316
  elif n==1110:
    return modarr317
  elif n==1101:
    return modarr318
  elif n==1011:
    return modarr319
  elif n==111:
    return modarr320
  elif n==111100:
    return modarr41
  elif n==111010:
    return modarr42
  elif n==111001:
    return modarr43
  elif n==110110:
    return modarr44
  elif n==110101:
    return modarr45
  elif n==110011:
    return modarr46
  elif n==101110:
    return modarr47
  elif n==101101:
    return modarr48
  elif n==101011:
    return modarr49
  elif n==100111:
    return modarr410
  elif n==11110:
    return modarr411
  elif n==11101:
    return modarr412
  elif n==11011:
    return modarr413
  elif n==10111:
    return modarr414
  elif n==1111:
    return modarr415
  elif n==111110:
    return modarr51
  elif n==111101:
    return modarr52
  elif n==111011:
    return modarr53
  elif n==110111:
    return modarr54
  elif n==101111:
    return modarr55
  elif n==11111:
    return modarr56

s=input()
l=len(s)
if l%6!=0:
  s='0'*(6-l%6)+s
  l+=(6-l%6)
mod=10**9+7
cnt=0
dp=[[0]*13 for _ in range(l//6+1)]
for i in range(l-1,-1,-6):
  num=0
  qpos=0
  for j in range(6):
    if s[i-j]=='?':
      qpos+=1*(10**j)
    else:
      num+=int(s[i-j])*(10**j)
  if qpos==0:
    tmod=[0]*13
    tmod[num%13]=1
  elif qpos==111111:
    tmod=modarr61
  else:
    tpos=num%13
    tmod=makemod(qpos)
    tmod=tmod[-tpos:]+tmod[:-tpos]
  if cnt==0:
    dp[1]=tmod
  else:
    for k in range(13):
      for l in range(13):
        dp[cnt+1][(k+l)%13]+=(tmod[k]*dp[cnt][l])%mod
  cnt+=1
print(dp[cnt][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 ind,s in enumerate(S):
    if(s=='?'):
        for i in range(10):
            for j in range(13):
                dp[ind+1][(j*10+i)%13] += dp[ind][j]
                dp[ind+1][(j*10+i)%13] %= mod
    else:
        for j in range(13):
            dp[ind+1][(j*10+int(s))%13] += dp[ind][j]
            dp[ind+1][(j*10+int(s))%13] %= mod
print(dp[n][5])