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:
#D問題
mod = 1000000007
S = str(input())
N = len(S)


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

    for k in range(13):
        dp[i+1][k]%=mod
            
print(dp[N][5]%mod)

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:
s = list(input())
n = len(s)
s.reverse()
m = 10**9 + 7
p = 10
dp = [[0 for i in range(13)] for j in range(n)]
if s[0] == "?":
    for i in range(10):
        dp[0][i] = dp[0][i] + 1
else:
    s0 = int(s[0])
    dp[0][s0] = dp[0][s0] + 1
for i in range(1,n):
    if s[i] != "?":
        s1 = int(s[i])
        k = (s1*p)%13
        for j in range(13):
            dp[i][(j+k)%13] = dp[i-1][j]
    else:
        for x in range(10):
            k = (x*p)%13
            for j in range(13):
                dp[i][(j+k)%13] += dp[i-1][j]
                dp[i][(j+k)%13] %= m
    p = (p * 10) % 13
print(dp[n-1][5])

Submission status: Accepted

Solution code:
import copy
MOD = 10**9+7
s = list(input())
n = len(s)
s.reverse()
dp = []
tem = []
for i in range(13):
    tem.append(0)
for i in range(n+1):
  dp.append(copy.copy(tem))
dp[0][0]=1
beki = 1
for i in range(1,n+1):
    if s[i-1] != "?":
        s1 = int(s[i-1])
        k = (s1*beki)%13
        for j in range(13):
            dp[i][(j+k)%13] = dp[i-1][j]
            #print(dp[i][(j+k)%13])
            dp[i][(j+k)%13]%=MOD
    else:
        for j in range(10):
            k = (j*beki)%13
            for x in range(13):
                dp[i][(x+k)%13] += dp[i-1][x]
                dp[i][(x+k)%13]%=MOD
    beki=beki*10
    beki%=13
    #print(dp[i])
print(dp[n][5])

Submission status: Accepted

Solution code:
S = input()


table = {}
pairs = [[((i*10 + j)%13, i) for i in range(13)] for j in range(13)]
mod = 10**9 + 7
for i in range(13):
    table[i] = tuple((i + j*13)//10 for j in range(10))

dp =[[0 for i in range(13)] for i in range(len(S))]

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

for i in range(1, len(S)):
    s = S[i]
    if s == "?":
        for j in range(13):
            for k in table[j]:
                dp[i][j] += dp[i-1][k] % mod
    else:
        s = int(s)
        for pair in pairs[s]:
            dp[i][pair[0]] = dp[i-1][pair[1]] % mod

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

Submission status: Accepted

Solution code:
S = input()


table = {}
pairs = [[((i*10 + j)%13, i) for i in range(13)] for j in range(13)]
mod = 10**9 + 7
for i in range(13):
    table[i] = tuple((i + j*13)//10 for j in range(10))

dp =[[0 for i in range(13)] for i in range(len(S))]

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

for i in range(1, len(S)):
    s = S[i]
    if s == "?":
        for j in range(13):
            for k in table[j]:
                dp[i][j] += dp[i-1][k]
            dp[i][j] %= mod
    else:
        s = int(s)
        for pair in pairs[s]:
            dp[i][pair[0]] = dp[i-1][pair[1]] % mod

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 1000000007
s = str(input())
n = len(s)
dp = [[0 for i in range(13)] for j in range(n + 1)]

dp[0][0] = 1
for i in range(n):
    c = -1 if s[i] == "?" else 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:
M=10**9+7
r=tuple(tuple((j-k)*9%13for j in range(10))for k in range(13))
d=[1]+[0]*12
for c in input():
    if c>'9':
        d=[sum(d[j]for j in k)%M for k in r]
    else:
        d=[d[(int(c)-k)*9%13]for k in range(13)]
print(d[5])

Submission status: Accepted

Solution code:
def main():
  M=10**9+7
  r=tuple(tuple((j-k)*9%13for j in range(10))for k in range(13))
  d=[1]+[0]*12
  for c in input():
    if c>'9':
      d=[sum(d[j]for j in k)%M for k in r]
    else:
      d=[d[(int(c)-k)*9%13]for k in range(13)]
  print(d[5])
main()

Submission status: Accepted

Solution code:
S = [int(x) if x != '?' else - 1 for x in input()]

dp=[(i,0) for i in range(13)]
dp=dict(dp)
dp[0]=1

i=0
mul=1

for k in reversed(S):
    newdp=dict([(i,0) for i in range(13)])
    if k==-1:
        for s in range(10):
            for j in range(13):               
                newdp[(mul*s + j) % 13] += dp[j]%(10**9+7)
    else:
        for j in range(13):
            newdp[(mul*k + j) % 13] += dp[j]%(10**9+7)
    dp=newdp
    mul = (mul *10)%13


print(dp[5]%(10**9+7))

Submission status: Accepted

Solution code:

N=input()

lists = []
temp=[i for i in range(10)]

MOD=10**9+7

dic={0:1}

for i in N:
    new_dic={}
    hoge=list(dic.items())
    if i == "?":
        for amari,count in hoge:
            amari*=10
            for num in temp:
                a = (amari + num) % 13
                if a in new_dic:
                    new_dic[a]+=count
                else:
                    new_dic[a]=count
    else:
        num=int(i)
        for amari,count in hoge:
            a = (amari*10 + num)%13
            if a in new_dic:
                new_dic[a]+=count
            else:
                new_dic[a]=count
    for key in new_dic:
        new_dic[key] %= MOD
    dic = new_dic

try:
    print(dic[5])
except:
    print(0)

Submission status: Accepted

Solution code:
S = input()
#S = "19?04??????451??" * (10 ** 5 // 5)
mod = 10 ** 9 + 7
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
#print(dp)
for i in range(len(S) - 1):
  if S[i + 1] == "?":
    for j in range(13):
      for k in range(10):
        dp[i + 1][(j * 10 + k) % 13] += dp[i][j] % mod
  else:
    for j in range(13):
      dp[i + 1][(j * 10 + int(S[i + 1])) % 13] += dp[i][j] % mod
#print(dp)
print(dp[len(S) - 1][5] % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
MOD = 10**9+7
s = input()
sl = list(s)
n=len(s)
dsl={i:sl[i] for i in range(n)}

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

dp[0][0]=1
for i in range(n):
    for k in range(10):
        if dsl[i] != "?" and dsl[i] != str(k):
            continue
        for j in range(13):
            dp[i+1][(j*10+k)%13] += dp[i][j]%MOD

print(dp[n][5]%MOD)

Submission status: Accepted

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

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

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

for i in range(2, lenS+1):
    chara = S[i-1]
    if chara=='?':
        for d in range(13):
            for e in range(10):
                newd = (d*10+e)%13
                dp[i][newd] = (dp[i][newd]+dp[i-1][d])%div
    else:
        for d in range(13):
            newd = (d*10+int(chara))%13
            dp[i][newd] = (dp[i][newd]+dp[i-1][d])%div

print(dp[-1][5])

Submission status: Accepted

Solution code:
#45 ABC135D 桁DP
s=input()
n=len(s)
dp=[[0 for _ in range(13)] for _ in range(n+1)]
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 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)
print(dp[n][5]%(10**9+7))

Submission status: Accepted

Solution code:
S=input()
N=len(S)
dp=[[0 for i in range(13)] for j in range(N+1)]
q=[(i*10)%13 for i in range(13)]
r=[q.index(i) for i in range(13)]
MOD=10**9+7
if S[0]=="?":
  dp[1]=[1,1,1,1,1,1,1,1,1,1,0,0,0]
else:
  dp[1][int(S[0])]=1
for i in range(2,N+1):
  if S[i-1]=="?":
    for j in range(13):
      for x in range(10):
        dp[i][(x+q[j])%13]+=dp[i-1][j]
    dp[i]=[dp[i][j]%MOD for j in range(13)]
  else:
    for j in range(13):
      x=int(S[i-1])
      dp[i][(x+q[j])%13]=dp[i-1][j]
print(dp[N][5])

Submission status: Accepted

Solution code:
s = input()
s = s[::-1]
mod = 10 ** 9 + 7
table = [[0] * 13 for _ in range(len(s) + 2)]
table[0][0] = 1
dd = 1
for c in range(len(s)):
    if s[c] == "?":
        for n in range(10):
            for i in range(13):
                table[c + 1][(i + n * dd) % 13] += table[c][i]
                table[c + 1][(i + n * dd) % 13] %= mod
    else:
        num = int(s[c])
        for i in range(13):
            table[c + 1][(i + num * dd) % 13] += table[c][i]
            table[c + 1][(i + num * dd) % 13] %= mod
    dd = (dd * 10) % 13
print(table[c + 1][5])

Submission status: Accepted

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

dd = 1

for i in range(len(S)):
    if S[i] == '?':
        for j in range(13):
            for k in range(10):
                table[i+1][(j + dd * k)  % 13] += table[i][j]
                table[i+1][(j + dd * k)  % 13] %= mod
    else:
        num = int(S[i])
        for j in range(13):
            table[i+1][(j + dd * num)  % 13] += table[i][j]
            table[i+1][(j + dd * num)  % 13] %= mod

    dd = (dd * 10) % 13

print(table[i+1][5])

Submission status: Accepted

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

dd = 1

for i in range(N):
    if S[i] == '?':
        for k in range(10):
            for j in range(13):
                table[i+1][(j + dd * k)  % 13] += table[i][j]
                table[i+1][(j + dd * k)  % 13] %= mod
    else:
        num = int(S[i])
        for j in range(13):
            table[i+1][(j + dd * num)  % 13] += table[i][j]
            table[i+1][(j + dd * num)  % 13] %= mod

    dd = (dd * 10) % 13

print(table[N][5])

Submission status: Accepted

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

dd = 1

for i in range(N):
    if S[i] == '?':
        for j in range(13):
            for k in range(10):
                table[i+1][(j + dd * k)  % 13] += table[i][j]
                table[i+1][(j + dd * k)  % 13] %= mod
    else:
        num = int(S[i])
        for j in range(13):
            table[i+1][(j + dd * num)  % 13] += table[i][j]
            table[i+1][(j + dd * num)  % 13] %= mod

    dd = (dd * 10) % 13

print(table[N][5])

Submission status: Accepted

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

dd = 1

for i in range(N):
    c = S[i] != '?'
    for j in range(13):
        for k in range(10):
            if c and int(S[i]) != k:
                continue
            table[i+1][(j + dd * k)  % 13] += table[i][j]
            table[i+1][(j + dd * k)  % 13] %= mod
    dd = (dd * 10) % 13

print(table[N][5])

Submission status: Accepted

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

dd = 1

for i, char in enumerate(reversed(S)):
    c = char != '?'
    for j in range(13):
        for k in range(10):
            if c and int(char) != k:
                continue
            table[i+1][(j + dd * k)  % 13] += table[i][j]
            table[i+1][(j + dd * k)  % 13] %= mod
    dd = (dd * 10) % 13

print(table[N][5])

Submission status: Accepted

Solution code:
from copy import deepcopy

S = input()

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

tens_mod = [1, 10, 9, 12, 3, 4]
mod = int(10**9 + 7)

for i, s in enumerate(S[::-1]):
    if s == "?":
        for j in range(13):
            dp[j] = 0
            for k in range(10):
                dp[j] += dp_past[(j - k * tens_mod[i % 6]) % 13]
            dp[j] %= mod

    else:
        k = int(s)
        for j in range(13):
            dp[j] = dp_past[(j - k * tens_mod[i % 6]) % 13]
    dp_past = deepcopy(dp)

print(dp[5] % mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
MOD = 10**9 + 7


def main():
    S = input().rstrip()
    DP = [0] * 13
    n = len(S)
    DP[0] = 1

    for i in range(0, n):
        preDP = DP
        DP = [0] * 13
        if S[i] == '?':
            for k in range(13):
                for x in range(10):
                    t = (x + 10*k) % 13
                    DP[t] += preDP[k]
                    DP[t] %= MOD
        else:
            y = int(S[i])
            for k in range(13):
                t = (y+10*k) % 13
                DP[t] += preDP[k]
                DP[t] %= MOD

    ans = DP[5]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

remainder = {0: 1}

for s in S:
    rx = {r: 0 for r in range(13)}
    for n in (range(10) if s == '?' else [int(s)]):
        for r in remainder:
            r2 = (r * 10 + n) % 13
            rx[r2] += remainder[r]
            rx[r2]  = rx[r2] % modulo
    remainder = rx

print(remainder[5] % modulo)

Submission status: Accepted

Solution code:
#10:30
s = input()
n = len(s)
now = [1,0,0,0,0,0,0,0,0,0,0,0,0]
for i in range(n):
  last = now
  now = [0 for _ in range(13)]
  here = s[i]
  if here == '?':
    for k in range(10):
      for j in range(13):
        now[(10*j+k)%13] += last[j]
  else:
    k = int(here)
    for j in range(13):
      now[(10*j+k)%13] += last[j]
  for j in range(13):
    now[j] %= 10**9+7
print(now[5])

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


def main(s):
    reminder = [[(j - k) * 9 % 13 for j in range(10)] for k in range(13)]
    dp = [1] + [0] * 12
    for char in s:
        if char == "?":
            dp = [sum(dp[j] for j in k) % MOD for k in reminder]
        else:
            dp = [dp[(int(char) - k) * 9 % 13] for k in range(13)]

    return dp[5]


S = input()
print(main(S))

Submission status: Accepted

Solution code:

P_MOD = 1000000007


def solve(S):
    # print(S)
    # 1, 10, 100, 1000, ... を 13 で割った値は 1, 10, 9, 12, 3, 4 で巡回する
    MODS = [1, 10, 9, 12, 3, 4]

    # 現在の桁の余り N の状態を cur[N]
    # 直前の桁の余り N の状態を priv[N] とする
    priv = [1] + [0] * 12
    # print(priv)
    s = S[::-1]
    for i in range(0, len(s)):
        cur = [0] * 13
        d = s[i]
        # print('i=', i, 'd=', d)
        if d == '?':
            for j in range(13):
                for di in range(10):
                    m = di * MODS[i % 6]
                    cur[(j+m) % 13] += priv[j]
        else:
            m = int(d) * MODS[i % 6]
            for j in range(13):
                cur[(m+j) % 13] = priv[j]
        # print(cur)
        for j in range(13):
            priv[j] = cur[j] % P_MOD
    return cur[5]


if __name__ == '__main__':
    S = input()

    ans = solve(S)

    print(ans % P_MOD)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

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

for i,s in enumerate(S):
    m = pow(10,(N-i-1),13)
    if s == '?':
        for d in range(10):
            for k in range(13):
                dp[i+1][(k+m*d)%13] += dp[i][k]
    else:
        d = int(s)
        for k in range(13):
            dp[i+1][(k+m*d)%13] += dp[i][k]

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


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

Submission status: Accepted

Solution code:
S = [int(x) if x != "?" else -1 for x in input()]
mod = int(1e9+7)
r = [0]*13
if S[0] != -1:
    r[S[0]] = 1
else:
    for i in range(10):
        r[i] = 1
for i in range(1, len(S)):
    dp = [0] * 26
    for j in range(13):
        dp[j * 10 % 13] += (r[j] % mod)

    dp[13:26] = dp[0:13]
    r = [0]*13
    if S[i] == -1:
        s = sum(dp[4:14])
        for j in range(13):
            r[j] += s
            s += dp[j+1] - dp[4+j]
    else:
        for j in range(13):
            r[j] += dp[13 - S[i] + j]
print(r[5] % mod)

Submission status: Accepted

Solution code:
#coding utf-8
S=list(input().strip())
S=[0]+S
l=len(S)
mod=10**9+7

dp=[[0 for i in range(13)] for j in range(l+1)]

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

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

Submission status: Accepted

Solution code:
N = input()[::-1]
iv = 1
MOD = 10**9+7
dp = [0]*13
dp[0]=1
ls = [0]*13
for i in range(len(N)):
  x = N[i]
  
  if x=='?':
    for j in range(13):
      for h in range(10):
        ls[(h*iv+j)%13] += dp[j]
        
  else:
    x = int(x)
    for j in range(13):
      ls[(j+x*iv)%13]+=dp[j]
      
  for j in range(13):
    dp[j] = (ls[j]%MOD)
  ls = [0]*13
  iv *= 10
  iv %= 13
print(dp[5])

Submission status: Accepted

Solution code:
N = input()[::-1]
iv = 1
MOD = 10**9+7
dp = [0 for i in range(13)]
dp[0]=1
ls = [0 for i in range(13)]
for i in range(len(N)):
  x = N[i]
  if x=='?':
    for j in range(13):
      for h in range(10):
        ls[(h*iv+j)%13] += dp[j]
    for j in range(13):
      dp[j] = (ls[j]%MOD)
      ls[j] = 0
  else:
    x = int(x)
    for j in range(13):
      ls[(j+x*iv)%13]+=dp[j]
    for j in range(13):
      dp[j] = (ls[j]%MOD)
      ls[j]=0
  iv *= 10
  iv %= 13
print(dp[5])

Submission status: Accepted

Solution code:
import numpy as np
import sys
def input():
    return sys.stdin.readline()[:-1]

# S = [int(x) if x!="?" else -1 for x in input()]

# print (S)

# div_num = 1000000007
# arr = np.arange(13, dtype = np.uint64)
# # dp = np.zeros([2, 13], dtype = np.uint64)

# div13_list = [1]
# for ii in range(1, len(S)):
#     n = div13_list[-1] * 10 % 13
#     if n in div13_list:
#         break
#     else:
#         div13_list.append(n)
# div13_mat = np.array([div13_list] * 10, dtype = int)
# div13_mat = (div13_mat * np.arange(10)[:, None] % 13).T

# if S[-1] == -1:
#     dp[0, :10] = 1
# else:
#     dp[0, S[-1]] = 1

# for ii in range(1, len(S)):
#     # ind = -ii-1
#     # tmp = div13_mat[ii%6]
#     # if S[ind] == -1:
#     #     for n in range(10):
#     #         res = np.roll(arr, -tmp[n])
#     #         # dp[1, res] += dp[0, arr]
#     # else:
#     #     res = np.roll(arr, -tmp[S[ind]])
#     #     # dp[1, res] += dp[0, arr]
#     dp[0] = dp[1] % div_num
#     dp[1] = 0


# print (dp[0, 5])

#
# 大きい方の桁からやってく方法
#

MOD = 1000000007;

S = [int(x) if x!="?" else -1 for x in input()]
n = len(S)

# r[i]
# 現在考えてる一つ前の桁数で、余りが i になる整数の個数
r = [0] * 13

# まず一つ目の値が１の位とする
s = S[0]
if (s != -1):
    r[s] = 1
else:
    for i in range(10): r[i] = 1

# 桁を進めながら個数をカウント
for i in range(1, n):
    # dp[j]
    # 現在考えている桁(i)を除く、余りが j となる整数の個数
    dp = [0] * 26

    # 桁が一つ上がるので、一つ前の余りが 10 倍になる
    for j in range(13):
        dp[j*10%13] += r[j] % MOD

    # アクセスを高速にするため２倍の長さとる (dp[i] == dp[i + 13])
    dp[13:26] = dp[0:13]

    r = [0]*13

    s = S[i]
    if (s == -1):
        w = sum(dp[4:14])
        for j in range(13):
            r[j] += w
            w += dp[j + 1]-dp[j + 4]
    else:
        for j in range(13):
            r[j] += dp[13-s+j]
print (r[5]%MOD)

Submission status: Accepted

Solution code:
from sys import stdin
S = (stdin.readline().rstrip())
dp = [[0]*13 for i in range(len(S)+1)]
MOD = 10**9+7
 
S = list(reversed(S))
dp[0][0] = 1
 
t = 1
for i, c in enumerate(S, 1):
    for j in range(13):
        if c == "?":
            for k in range(10):
                nj = (k*t+j) % 13
                dp[i][nj] = dp[i][nj] + dp[i-1][j]
                dp[i][nj] %= MOD
        else:
            nj = (int(c)*t+j) % 13
            dp[i][nj] = dp[i][nj] + dp[i-1][j]
            dp[i][nj] %= MOD
    t = (t*10)%13
print(dp[-1][5])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
S=raw_input()
l=len(S)

dp=[ [ 0 for j in range(13)] for i in range(l+1) ]
dp[0][0]=1

mod=10**9+7
keta=pow(10,l-1,13)

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

	keta=(keta*4)%13	#フェルマーの小定理より 10*(10**(p-1))=1(mod p)   p=13　なので、10**11(mod13)が、10の逆元

print dp[-1][5]

Submission status: Accepted

Solution code:
S=raw_input()
S=S[::-1]
l=len(S)

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

mod=10**9+7

dp2=[ 0 for _ in range(13) ]

keta=1

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

	dp=dp2
	keta=(keta*10)%13

print dp[5]

Submission status: Accepted

Solution code:
def main():
    M=10**9+7
    r=tuple(tuple((j-k)*9%13 for j in range(10))for k in range(13))
    d=[1]+[0]*12
    for c in input():
      if c>'9':
        d=[sum(d[j]for j in k)%M for k in r]
      else:
        d=[d[(int(c)-k)*9%13]for k in range(13)]
    print(d[5])
main()

Submission status: Accepted

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

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


dp[0][0] = 1

for i,s in enumerate(ss):
    if s == "?":
        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))%13] += dp[i][k] % MOD
            

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

Submission status: Accepted

Solution code:
import itertools

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

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):
    c = -1 if s[i] == '?' else ord(s[i]) - ord('0')
    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

res = dp[n][5]

print(res)

Submission status: Accepted

Solution code:
import numpy as np


def main():
    n = 13
    mod = 1000000007
    r = 5
    in_str = input()

    amari_l = amari_list(n)
    amari_m = amari_matrix(n, amari_l)

    ans_list = initial(in_str[-1:], n)

    for i, s in enumerate(reversed(in_str)):
        if i == 0:
            continue
        if s == "?":
            ans_list = np.dot(ans_list, amari_m[i % len(amari_m)]) % mod
        else:
            t = int(s) * amari_l[i % len(amari_l)] % n
            ans_list = np.roll(ans_list, t)

    print(int(ans_list[r] % mod))


def initial(s, n):
    if s == "?":
        return np.array([1 if i < 10 else 0 for i in range(n)], dtype='int64')
    else:
        return np.array([1 if i == int(s) else 0 for i in range(n)], dtype='int64')


def shift(n, r):
    return np.array([[1 if (i - j + r) % n == 0 else 0 for j in range(n)] for i in range(n)])


def amari_list(n):
    ret = []
    for i in range(n + 1):
        r = 10**i % n
        if r in ret:
            return ret
        else:
            ret.append(r)


def amari_matrix(n, amari_list):
    ret = np.zeros((len(amari_list), n, n))
    for i, j in enumerate(amari_list):
        tmp = np.zeros((n, n))
        for k in range(10):
            tmp += shift(n, j * k % n)
        ret[i] = tmp
    return ret


if __name__ == '__main__':
    main()

Submission status: Accepted

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

for i in range(len(S)):
    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[len(S)][5])

Submission status: Accepted

Solution code:
ll = list(input())

count = {}

for i in range(13):
    count[i] = 0

count[0] = 1

for i in ll:

    new_count = {}
    
    for j in range(13):
        new_position = (j * 10) % 13
        new_count[new_position] = count[j]

    count = new_count.copy()

    new_count = {}
    
    if i.isdigit():
        i_int = int(i)
        for j in range(13):
            new_position = (i_int + j) % 13
            new_count[new_position] = count[j]
            
    else:
        for j in range(13):
            new_count[j] = 0
            
        for k in range(10):
            for j in range(13):
                new_position = (k + j) % 13
                new_count[new_position] += count[j]            
    
    count = new_count.copy()
    
    for i in range(13):
        count[i] = count[i] % (10 ** 9 + 7)
    
print(count[5])

Submission status: Accepted

Solution code:
import math
MOD = 10**9+7
s = [int(x) if x!="?" else -1 for x in input()]
n =len(s)
A=13
data=[4,3,12,9,10,1]*math.ceil(n/6)
data=data[-n:]

dp=[[0 for i in range(A+1)] for j in range(n+1)]
dp[0][0]=1

def benri(a,i,j):
	if j-a*data[i]%A>=0:
		re = j-a*data[i]%A
	else:
		re = j-a*data[i]%A+13
	return re

for i in range(n):
	for j in range(A+1):
		if s[i]!=-1:
			dp[i+1][j]=dp[i][benri(s[i],i,j)]%MOD

		else:
			for c in range(10):
				dp[i+1][j]+=dp[i][benri(c,i,j)]%MOD

			
			
# print(dp)
print(dp[n][5]%MOD)

Submission status: Accepted

Solution code:
MOD = 1000000007;
 
s = [int(x) if x!="?" else -1 for x in input()]
#print(s)
n=len(s)
 
r=[0]*13
 
c=s[0]
if (c!=-1):
    r[c]=1
else:
    for i in range(10):r[i]=1
for i in range(1,n):
    dp=[0]*26
    for j in range(13):dp[j*10%13]+=(r[j]%MOD)
    dp[13:26]=dp[0:13]
    c=s[i]
    r=[0]*13
    if (c==-1):
        w=sum(dp[4:14])
        for j in range(13):
            r[j]+=w
            w=w+dp[j+1]-dp[4+j]
    else:
        for j in range(13):
            r[j]+=dp[13-c+j]
print (r[5]%MOD)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

R10 = range(10)
R13 = range(13)

S = input()
R = [[(M-N)*4 % 13 for N in R10] for M in R13]
AM = 10**9+7

MOD =[1]+[0]*12

for D in S:
    if D == '?':
        MOD = [sum([MOD[N] for N in M])%AM for M in R]
    else:
        C = int(D)
        MOD = [MOD[M[C]] for M in R]
    #end if
#end for

print(MOD[5])

Submission status: Accepted

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

M = 1
INF = 10 ** 9 + 7
      
for i in range(n):
  if s[n-1-i] == '?':
    for k, j in itertools.product(range(10), range(13)):
      x = (j+k*M)%13
      dp[i+1][x] += dp[i][j]
      dp[i+1][x] %= INF
  else:
    for j in range(13):
      x = (j+int(s[n-1-i])*M)%13
      dp[i+1][x] += dp[i][j]
      dp[i+1][x] %= INF
  M = (M*10)%13

print(dp[-1][5])
#print(dp[-1][5]%(10**9+7))
#print(dp)

Submission status: Accepted

Solution code:
MOD = 1000000007

s = [-1 if x == '?' else int(x) for x in input()]
n = len(s) + 1

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

r = [[(j-i)*4%13 for i in range(10)]for j in range(13)]

for i, x in enumerate(s):
    next_dp = [0] * 13
    if x == -1:
        next_dp = [sum(dp[i] for i in j) for j in r]
    else:
        next_dp = [dp[j[x]] for j in r]
    dp = [k % MOD for k in next_dp]

print(dp[5])

Submission status: Accepted

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

dp = [0]*13
flag = 0
for s in S:
    if flag == 0:
        if s == "?":
            dp = [1 for _ in range(10)]+[0]*3
        else:
            s = int(s)
            dp[s%13] = 1
        flag = 1
    else:
        prev = dp
        dp = [0]*13
        if s == "?":
            for i in range(13):
                for j in range(10):
                    dp[(10*i+j)%13] += prev[i]
        else:
            s = int(s)
            for i in range(13):
                dp[(10*i+s)%13] += prev[i]
        dp = [x % MOD for x in dp]
print(dp[5])

Submission status: Accepted

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

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

for s in S:
    prev = [x for x in dp]
    dp = [0]*13
    if s == "?":
        r = range(10)
    else:
        r = [int(s)]
    for i in range(13):
        for x in r:
            dp[(10*i+x)%13] += prev[i]
    dp = [x % MOD for x in dp]
print(dp[5])

Submission status: Accepted

Solution code:
x = 1000000007

S = input()
S = [int(s) if s != '?' else s for s in S]

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

for i, s in enumerate(S):
    for j in range(10):
        if s != '?' and s != j:
            continue

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

print(int(dp[-1][5] % x))