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: Wrong Answer

Solution code:
MOD=1000000007
s = [int(x) if x!="?" else -1 for x in input()]
n=len(s)
dp=[[0 for j in range(13)] for i in range(n+1)]
dp[0][0]=1
for i in range(n):

  for j in range(13):
    #　i+1番目が？のときは０〜９の可能性
    if s[i]==-1:
      for k in range(10):
        dp[i+1][((j*10)%13+k)%13]+=dp[i][j]%MOD
        

    #  i+1番目が?じゃないとき
    else:
      dp[i+1][((j*10)%13+s[i])%13]+=dp[i][j]

print(dp[n][5])

Submission status: Wrong Answer

Solution code:
s = [int(x) if x!="?" else -1 for x in input()]
n=len(s)
dp=[[0 for j in range(13)] for i in range(n+1)]
dp[0][0]=1
for i in range(n):

  for j in range(13):
    #　i+1番目が？のときは０〜９の可能性
    if s[i]==-1:
      for k in range(10):
        dp[i+1][((j*10)%13+k)%13]+=dp[i][j]

    #  i+1番目が?じゃないとき
    else:
      dp[i+1][((j*10)%13+s[i])%13]+=dp[i][j]

print(dp[n][5])

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
# ? だったら -1
S = [int(x) if x != "?" else -1 for x in input()]

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

# i文字目, 13で割った余りがj

for i in range(len(S)):
    #
    if S[i] == -1:
        # 0 ~ 9の数字が入ることを考える
        for n in range(10):
            # 余りは0 ~ 12 が入る
            for j in range(13):
                dp[i+1][(j*10+n) % 13] += dp[i][j]
    else:
        n = S[i]
        for j in range(13):
            dp[i+1][(j*10+n) % 13] += dp[i][j]

print(dp)

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

Submission status: Wrong Answer

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

mod = 1000000007
length = len(s)
ans = list([0]*13 for i in range(length+1))
ans[0][0] = 1

mod_x10 = [0]*13
for i in range(13):
    mod_x10[i] = i * 10 % 13 - 14

for i in range(length):
    if s[i] == -1:
        for j in range(13):
            x = mod_x10[j]
            for k in range(10):
                x = x + 1
                ans[i+1][x] += ans[i][j] % mod
    else:
        for j in range(13):
            ans[i+1][(mod_x10[j] + s[i] + 1) % 13] += ans[i][j] % mod

print('a')
print(ans[length][5] % mod)

Submission status: Wrong Answer

Solution code:
s = input()

question_offset = []
count = 0

for offset, c in enumerate(s):
    if c == '?':
        question_offset.append(offset)

start = int(s.replace("?", "0"))
end = int(s.replace("?", "9"))

def check(str1, str2):
    if len(str1) != len(str2):
        return False

    for c1, c2 in zip(str1, str2):
        if c1 == '?':
            continue
        else:
            if c1 == c2:
                continue
            else:
                return False
    else:
        return True

array = [i for i in range(5, end, 13) if check(s, format(i, '0'+str(len(s))))]

print(len(array) % (10**9+7))

Submission status: Wrong Answer

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

mod = 1000000007
length = len(s)
ans = list([0]*13 for i in range(length+1))
ans[0][0] = 1

mod_x10 = [0]*13
for i in range(13):
    mod_x10[i] = i * 10 % 13 - 1

for i in range(length):
    if s[i] == -1:
        for j in range(13):
            x = mod_x10[j]
            for k in range(10):
                x = (x + 1) % 13
                ans[i+1][x] += ans[i][j] % mod
    else:
        for j in range(13):
            x = (mod_x10[j] + s[i] + 1) % 13
            ans[i+1][x] += ans[i][j] % mod

print('a')
print(ans[length][5] % mod)

Submission status: Wrong Answer

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

mod = 1000000007
length = len(s)
ans = list([0]*13 for i in range(length+1))
ans[0][0] = 1

mod_x10 = [0]*13
for i in range(13):
    mod_x10[i] = i * 10 % 13 - 1

for i in range(length):
    for j in range(13):
        x = mod_x10[j]
        if s[i] == -1:
            for k in range(10):
                x = (x + 1) % 13
                ans[i+1][x] += ans[i][j] % mod
        else:
            x = (x + s[i] + 1) % 13
            ans[i+1][x] += ans[i][j] % mod

print('a')
print(ans[length][5] % mod)

Submission status: Wrong Answer

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

mod = 1000000007
length = len(s)
ans = list([0]*13 for i in range(length+1))
ans[0][0] = 1

mod_x10 = [0]*13
for i in range(13):
    mod_x10[i] = i * 10 % 13 - 1

for i in range(length):
    for j in range(13):
        x = mod_x10[j]
        if s[i] == -1:
            for k in range(10):
                x = (x + 1) % 13
                ans[i+1][x] += ans[i][j] % mod
        else:
            x = (x + int(s[i]) + 1) % 13
            ans[i+1][x] += ans[i][j] % mod

print('a')
print(ans[length][5] % mod)

Submission status: Wrong Answer

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

mod = 1000000007
length = len(s)
ans = list([0]*13 for i in range(length+1))
ans[0][0] = 1

mod_x10 = [0]*13
for i in range(13):
    mod_x10[i] = i * 10 % 13 - 1

for i in range(length):
    for j in range(13):
        x = mod_x10[j]
        if s[i] == -1:
            for k in range(10):
                x = (x + 1) % 13
                ans[i+1][x] += ans[i][j]
        else:
            x = (x + int(s[i]) + 1) % 13
            ans[i+1][x] += ans[i][j]

print(ans[length][5] % mod)
print('a')

Submission status: Wrong Answer

Solution code:
S = input()
lenS = len(S)
#dp[k] ... 13で割った余りがkになる個数
dp = [0] * 13
dp[0] = 1
mod = 10**9+7
#1?2?3   0 -> 3 -> ?3 -> 2?3 -> ...
mul = 1
for i in range(lenS - 1, -1, -1):
    nextDP = [0] * 13
    if S[i] == "?":
        for k in range(10):
            for j in range(13):
                nextDP[(k * mul + j)%13] += dp[j]
                nextDP[(k * mul + j)%13] %= mod
    else:
        k = int(S[i])
        for j in range(13):
            nextDP[(k * mul + j)%13] += dp[j]
            nextDP[(k * mul + j)%13] %= mod
    mul *= 10
    mul %= mod
    dp = nextDP
print(dp[5])

Submission status: Wrong Answer

Solution code:
s = input()

question_offset = []
count = 0

for offset, c in enumerate(s):
    if c == '?':
        question_offset.append(offset)

start = int(s.replace("?", "0"))
end = int(s.replace("?", "9"))

def check(str1, str2):
    if len(str1) != len(str2):
        return False

    for c1, c2 in zip(str1, str2):
        if c1 == '?':
            continue
        else:
            if c1 == c2:
                continue
            else:
                return False
    else:
        return True

for i in range(5, end, 13):
    if check(s, format(i, '0'+str(len(s)))):
        count += 1

print(count%(pow(10,9)+7))

Submission status: Wrong Answer

Solution code:
s = input()

question_offset = []
count = 0

for offset, c in enumerate(s):
    if c == '?':
        question_offset.append(offset)

start = int(s.replace("?", "0"))
end = int(s.replace("?", "9"))

num = start

def check(str1, str2):
    if len(str1) != len(str2):
        return False

    for c1, c2 in zip(str1, str2):
        if c1 == '?':
            continue
        else:
            if c1 == c2:
                continue
            else:
                return False
    else:
        return True

for i in range(5, end, 13):
    if check(s, format(i, '0'+str(len(s)))):
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6) ################「再帰回数上限解放」######################

S = [int(x) if x != '?' else '?' for x in input()]
length = len(S)

A = [0] * 13
B = [0] * 13
mod = 5
first = 0
r = 1

for i in range(length):
    a = S[length - i- 1]
    if a != '?':
        a = (a * r) % 13
        mod -= a
        mod %= 13

    elif first == 0:
        for j in range(10):
            a = (j * r) % 13
            A[a] += 1
        first = 1

    else:
        for j in range(10):
            a = (j * r) % 13
            for k in range(13):
                B[(k + a) % 13] += A[k]
                B[(k + a) % 13] %= 10 ** 9 + 7
        A = B
        B = [0] * 13
    r = (r * 10) % 13

print(A[mod])

Submission status: Wrong Answer

Solution code:
s=input()
dp=[[0 for i in range(13)]for j in range(len(s)+1)]
ten=1
if s[-1]=="?":
  for i in range(13):
    dp[1][i]=1
else:
  dp[1][int(s[-1])]=1
if len(s)>=2:
  for i in range(2,len(s)+1):
    ten*=10
    if s[-1*i]=="?":
      for j in range(10):
        for k in range(13):
          dp[i][(ten*j+k)%13]+=dp[i-1][k]
    else:
      for j in range(13):
        dp[i][(ten*int(s[-1*i])+j)%13]+=dp[i-1][j]
print(dp[len(s)][5])

Submission status: Wrong Answer

Solution code:
from numpy import zeros

dp = {5:1}
mapper = {0: 0, 1: 9, 2: 5, 3: 1, 4: 10, 5: 6, 6: 2, 7: 11, 8: 7, 9: 3}
wildcard_mapper = {0: [0, 9, 5, 1, 10, 6, 2, 11, 7, 3],
             1: [4, 0, 9, 5, 1, 10, 6, 2, 11, 7],
             2: [8, 4, 0, 9, 5, 1, 10, 6, 2, 11],
             3: [12, 8, 4, 0, 9, 5, 1, 10, 6, 2],
             4: [3, 12, 8, 4, 0, 9, 5, 1, 10, 6],
             5: [7, 3, 12, 8, 4, 0, 9, 5, 1, 10],
             6: [11, 7, 3, 12, 8, 4, 0, 9, 5, 1],
             7: [2, 11, 7, 3, 12, 8, 4, 0, 9, 5],
             8: [6, 2, 11, 7, 3, 12, 8, 4, 0, 9],
             9: [10, 6, 2, 11, 7, 3, 12, 8, 4, 0],
             10: [1, 10, 6, 2, 11, 7, 3, 12, 8, 4],
             11: [5, 1, 10, 6, 2, 11, 7, 3, 12, 8],
             12: [9, 5, 1, 10, 6, 2, 11, 7, 3, 12]}
cache_mapper = {(0, 0): 0,
 (0, 1): 9,
 (0, 2): 5,
 (0, 3): 1,
 (0, 4): 10,
 (0, 5): 6,
 (0, 6): 2,
 (0, 7): 11,
 (0, 8): 7,
 (0, 9): 3,
 (1, 0): 4,
 (1, 1): 0,
 (1, 2): 9,
 (1, 3): 5,
 (1, 4): 1,
 (1, 5): 10,
 (1, 6): 6,
 (1, 7): 2,
 (1, 8): 11,
 (1, 9): 7,
 (2, 0): 8,
 (2, 1): 4,
 (2, 2): 0,
 (2, 3): 9,
 (2, 4): 5,
 (2, 5): 1,
 (2, 6): 10,
 (2, 7): 6,
 (2, 8): 2,
 (2, 9): 11,
 (3, 0): 12,
 (3, 1): 8,
 (3, 2): 4,
 (3, 3): 0,
 (3, 4): 9,
 (3, 5): 5,
 (3, 6): 1,
 (3, 7): 10,
 (3, 8): 6,
 (3, 9): 2,
 (4, 0): 3,
 (4, 1): 12,
 (4, 2): 8,
 (4, 3): 4,
 (4, 4): 0,
 (4, 5): 9,
 (4, 6): 5,
 (4, 7): 1,
 (4, 8): 10,
 (4, 9): 6,
 (5, 0): 7,
 (5, 1): 3,
 (5, 2): 12,
 (5, 3): 8,
 (5, 4): 4,
 (5, 5): 0,
 (5, 6): 9,
 (5, 7): 5,
 (5, 8): 1,
 (5, 9): 10,
 (6, 0): 11,
 (6, 1): 7,
 (6, 2): 3,
 (6, 3): 12,
 (6, 4): 8,
 (6, 5): 4,
 (6, 6): 0,
 (6, 7): 9,
 (6, 8): 5,
 (6, 9): 1,
 (7, 0): 2,
 (7, 1): 11,
 (7, 2): 7,
 (7, 3): 3,
 (7, 4): 12,
 (7, 5): 8,
 (7, 6): 4,
 (7, 7): 0,
 (7, 8): 9,
 (7, 9): 5,
 (8, 0): 6,
 (8, 1): 2,
 (8, 2): 11,
 (8, 3): 7,
 (8, 4): 3,
 (8, 5): 12,
 (8, 6): 8,
 (8, 7): 4,
 (8, 8): 0,
 (8, 9): 9,
 (9, 0): 10,
 (9, 1): 6,
 (9, 2): 2,
 (9, 3): 11,
 (9, 4): 7,
 (9, 5): 3,
 (9, 6): 12,
 (9, 7): 8,
 (9, 8): 4,
 (9, 9): 0,
 (10, 0): 1,
 (10, 1): 10,
 (10, 2): 6,
 (10, 3): 2,
 (10, 4): 11,
 (10, 5): 7,
 (10, 6): 3,
 (10, 7): 12,
 (10, 8): 8,
 (10, 9): 4,
 (11, 0): 5,
 (11, 1): 1,
 (11, 2): 10,
 (11, 3): 6,
 (11, 4): 2,
 (11, 5): 11,
 (11, 6): 7,
 (11, 7): 3,
 (11, 8): 12,
 (11, 9): 8,
 (12, 0): 9,
 (12, 1): 5,
 (12, 2): 1,
 (12, 3): 10,
 (12, 4): 6,
 (12, 5): 2,
 (12, 6): 11,
 (12, 7): 7,
 (12, 8): 3,
 (12, 9): 12}
n = input().rstrip("\n")
rn = reversed(n)

m = 10 ** 9 + 7

dp = zeros((100005, 13) ,dtype=int)
dp[0][5] = 1
for i, c in enumerate(rn):
    if c == "?":
        for used in range(13):
            for next_used in wildcard_mapper[used]:
                dp[i+1][next_used] += dp[i][used]
    else:
        digit = int(c)
        for used in range(13):
            next_used = cache_mapper[(used,digit)]
            dp[i+1][next_used] += dp[i][used]
            
    for j in range(13):
        dp[i][j] %= m
print(dp[len(n)][0] % m)

Submission status: Wrong Answer

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！
 
def main():
    MOD=10**9+7
    s="0"+input()
    dp=[[0]*len(s)for i in range(13)]
    dp[0][0]=1
    for k,j in enumerate(s[1:]):
        if j=="?":
            for i in range(13):
                if dp[i][k]:
                    for r in range(10):
                        dp[int(str(i)+str(r))%13][k+1]+=dp[i][k]%MOD
        else:
            for i in range(13):
                if dp[i][k]:
                    dp[int(str(i)+j)%13][k+1]+=dp[i][k]%MOD
    print(dp[5][-1])
    
    
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
 
S = input()
MOD = 10**9 + 7
 
# 縦i,横j, 数字k
dp_ = [[0 for j in range(13)] for i in range(len(S)+1)]
dp_[0][0] = 1
dp = np.array(dp_, dtype=int)

for i in range(len(S)):
    if S[i] == '?':
        # for j in range(13):
        #    for k in range(10):
                # dp[i+1][(j*10 + k) % 13] += dp[i][j]
                # print("{} {}".format((j*10+k)%13, j))
        sum_ = np.sum(dp[i])
        dp[i+1][0] = sum_ - dp[i][4] - dp[i][8] - dp[i][12]
        dp[i+1][1] = sum_ - dp[i][3] - dp[i][8] - dp[i][12]
        dp[i+1][2] = sum_ - dp[i][3] - dp[i][7] - dp[i][11]
        dp[i+1][3] = sum_ - dp[i][3] - dp[i][7] - dp[i][11]
        dp[i+1][4] = sum_ - dp[i][2] - dp[i][7] - dp[i][11]
        dp[i+1][5] = sum_ - dp[i][2] - dp[i][6] - dp[i][11]
        dp[i+1][6] = sum_ - dp[i][2] - dp[i][6] - dp[i][11]
        dp[i+1][7] = sum_ - dp[i][1] - dp[i][6] - dp[i][10]
        dp[i+1][8] = sum_ - dp[i][1] - dp[i][5] - dp[i][10]
        dp[i+1][9] = sum_ - dp[i][1] - dp[i][5] - dp[i][9]
        dp[i+1][10] = sum_ - dp[i][0] - dp[i][5] - dp[i][9]
        dp[i+1][11] = sum_ - dp[i][0] - dp[i][4] - dp[i][9]
        dp[i+1][12] = sum_ - dp[i][0] - dp[i][4] - dp[i][8]
    else:
        for j in range(13):
            dp[i+1][(j * 10 + int(S[i])) % 13] += dp[i][j]
    for j in range(13):
        dp[i+1][j] %= MOD
 
print(dp[-1][5] % MOD)

Submission status: Wrong Answer

Solution code:
import numpy as np
 
S = input()
MOD = 10**9 + 7
 
# 縦i,横j, 数字k
dp_ = [[0 for j in range(13)] for i in range(len(S)+1)]
dp_[0][0] = 1
dp = np.array(dp_, dtype=int)

jk = [0] * 130

for i in range(len(S)):
    if S[i] == '?':
        for j in range(13):
            for k in range(10):
                # dp[i+1][(j*10 + k) % 13] += dp[i][j]
                # print("{} {}".format((j*10+k)%13, j))
                sum_ = np.sum(dp[i])
                dp[i+1][0] = sum_ - dp[i][4] - dp[i][8] - dp[i][12]
                dp[i+1][1] = sum_ - dp[i][3] - dp[i][8] - dp[i][12]
                dp[i+1][2] = sum_ - dp[i][3] - dp[i][7] - dp[i][11]
                dp[i+1][3] = sum_ - dp[i][3] - dp[i][7] - dp[i][11]
                dp[i+1][4] = sum_ - dp[i][2] - dp[i][7] - dp[i][11]
                dp[i+1][5] = sum_ - dp[i][2] - dp[i][6] - dp[i][11]
                dp[i+1][6] = sum_ - dp[i][2] - dp[i][6] - dp[i][11]
                dp[i+1][7] = sum_ - dp[i][1] - dp[i][6] - dp[i][10]
                dp[i+1][8] = sum_ - dp[i][1] - dp[i][5] - dp[i][10]
                dp[i+1][9] = sum_ - dp[i][1] - dp[i][5] - dp[i][9]
                dp[i+1][10] = sum_ - dp[i][0] - dp[i][5] - dp[i][9]
                dp[i+1][11] = sum_ - dp[i][0] - dp[i][4] - dp[i][9]
                dp[i+1][12] = sum_ - dp[i][0] - dp[i][4] - dp[i][8]
    else:
        for j in range(13):
            dp[i+1][(j * 10 + int(S[i])) % 13] += dp[i][j]
    for j in range(13):
        dp[i+1][j] %= MOD
 
print(dp[-1][5] % MOD)

Submission status: Wrong Answer

Solution code:
import numpy as np
S = input()[::-1]
mod = 1000000007

n = len(S)
a = S[0]
x = np.zeros(26, np.uint64)
l = [[13 - i * j % 13 for j in range(0, 10)] for i in [1, 10, 9, 12, 3, 4]] * (n // 6 + 1)
if a == "?":
    x[0:10] += 1
else:
    x[int(a)] += 1
for s, l_ in zip(S[1:], l[1:]):
    x[13:] = x[:13]
    if s == "?":
        x[:13] = sum([x[v:v+13] for v in l_])
    else:
        v = l_[int(s)]
        x[:13] = x[v:v+13]
#     x %= mod
print(x[5] % mod)

Submission status: Wrong Answer

Solution code:
import numpy as np
S = input()[::-1]
mod = 1000000007

n = len(S)
a = S[0]
x = np.zeros(26, int)
l = [[13 - i * j % 13 for j in range(0, 10)] for i in [1, 10, 9, 12, 3, 4]] * (n // 6 + 1)
if a == "?":
    x[0:10] += 1
else:
    x[int(a)] += 1
for s, l_ in zip(S[1:], l[1:]):
    x[13:] = x[:13]
    if s == "?":
        x[:13] = sum([x[v:v+13] for v in l_])
    else:
        v = l_[int(s)]
        x[:13] = x[v:v+13]
#     x %= mod
print(x[5] % mod)

Submission status: Wrong Answer

Solution code:
S = input()
N = 13
dp = [0] * N
dp[0] = 1
mul = 1
mod = 10 ** 9
for i in range(len(S)-1, -1, -1):
    i = int(i)
    nextDp = [0] * N
    char = S[i]
    if char == '?':
        for k in range(10):
            for j in range(N):
                nextDp[(k * mul + j)%13] += dp[j]
                nextDp[(k * mul + j)%13] %= mod
    else:
        k = int(S[i])
        for j in range(N):
            nextDp[(k * mul + j)%13] += dp[j]
            nextDp[(k * mul + j)%13] %= mod
    mul *= 10
    mul %= N
    dp = nextDp
print(dp[5])

Submission status: Wrong Answer

Solution code:
#%%time
mod=10**9+7
s=input()
#s="?"*10**5


#p=[[i*j%13 for i in range(10)] for j in range(13)]
rev=reversed(s)
d=[0 for i in range(13)]
d[0]=1
keep=[0 for _ in range(13)]
mul=1
cal=0
for v in rev:

    #print(i+num+1)
    if v=="?":
        t_d=keep.copy()
        #print("i,tmp:",i+num+1,",",tmp)
        for k in range(0,13):
            for j in range(0,10):
                t_d[(mul*j+k)%13]+=d[k]
            t_d[k]%=mod
        d=t_d
    else:
        cal+=mul*int(v)%13
    mul*=10
    mul%=13
        #print(t_d)
cal%=13
print(d[cal]%mod)
#print(d)
#h=d
#print([i%mod for i in h])

Submission status: Wrong Answer

Solution code:
s = [i for i in input()]
n =len(s)
A=13
data=[4,3,12,9,10,1]*n
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):
	return a*data[i]%A


for j in range(A+1):
	for i in range(n):
		if s[i]!="?":
			if j-benri(int(s[i]),i)>=0:
				dp[i+1][j]=dp[i][j-benri(int(s[i]),i)]
			else:
				dp[i+1][j]=dp[i][j-benri(int(s[i]),i)+13]

		else:
			for c in range(10):
				if j-benri(c,i)>=0:
					dp[i+1][j]+=dp[i][j-benri(c,i)]
				else:
					# print(j-c%13+13)
					dp[i+1][j]+=dp[i][j-benri(c,i)+13]

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

Submission status: Wrong Answer

Solution code:
s = [i for i in input()]
n =len(s)
A=13

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

for i in range(n):
	for j in range(A+1):
		if s[i]!="?":
			if j-int(s[i])*10**(len(s)-(i+1))%13>=0:
				dp[i+1][j]=dp[i][j-int(s[i])*10**(len(s)-(i+1))%13]
			else:
				dp[i+1][j]=dp[i][j-int(s[i])*10**(len(s)-(i+1))%13+13]

		else:
			for c in range(10):
				if j-c*10**(len(s)-(i+1))%13>=0:
					dp[i+1][j]+=dp[i][j-c*10**(len(s)-(i+1))%13]
				else:
					# print(j-c%13+13)
					dp[i+1][j]+=dp[i][j-c*10**(len(s)-(i+1))%13+13]

			
			

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

Submission status: Wrong Answer

Solution code:
s = [i for i in input()]
n =len(s)
A=13

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

for i in range(n):
	for j in range(A+1):
		if s[i]!="?":
			if j-int(s[i])*10**(len(s)-(i+1))%13>=0:
				dp[i+1][j]=dp[i][j-int(s[i])*10**(len(s)-(i+1))%13]
			else:
				dp[i+1][j]=dp[i][j-int(s[i])*10**(len(s)-(i+1))%13+13]

		else:
			for c in range(10):
				if j-c*10**(len(s)-(i+1))%13>=0:
					dp[i+1][j]+=dp[i][j-c*10**(len(s)-(i+1))%13]
				else:
					# print(j-c%13+13)
					dp[i+1][j]+=dp[i][j-c*10**(len(s)-(i+1))%13+13]

			
			

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

Submission status: Wrong Answer

Solution code:
s = input()

mod = 1000000007
length = len(s)
ans = list([0]*13 for i in range(length+1))
ans[0][0] = 1

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

print(ans[length][5] % mod)

Submission status: Wrong Answer

Solution code:
import numpy as np
S = input()
mod = 1000000007

n = len(S)
a = S[-1]
x = np.zeros(26, int)
l = [[13 - i * j % 13 for j in range(0, 10)] for i in [1, 10, 9, 12, 3, 4]] * (n // 6 + 1)
if a == "?":
    x[0:10] += 1
else:
    x[int(a)] += 1
for s, l_ in zip(S[-2::-1], l[1:]):
    x %= mod
    x[13:] = x[:13]
    if s == "?":
        x[:13] = sum([x[v:v+13] for v in l_])
    else:
        v = l_[int(s)]
        x[:13] = x[v:v+13]
print(x[5])

Submission status: Wrong Answer

Solution code:
import numpy as np
S = input()
mod = 10 ** 9 + 7

n = len(S)
dp = np.zeros((n, 26), int)
a = S[-1]
x_ = dp[0]
l = [1, 10, 9, 12, 3, 4]
l = [[13 - i * l_ % 13 for i in range(0, 10)] for l_ in l] * (n // 6 + 1)
if a == "?":
    x_[0:10] = 1
else:
    x_[int(a)] = 1
x_[13:] = x_[:13]
for s, x, l_ in zip(S[-2::-1], dp[1:], l[1:]):
    if s == "?":
        x[:13] = sum(x_[v:v + 13] for v in l_)
    else:
        v = l_[int(s) - 1]
        x[:13] += x_[v:v + 13]
    x %= mod
    x[13:] = x[:13]
    x_ = x
print(dp[-1][5])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6) ################「再帰回数上限解放」######################

S = [int(x) if x != '?' else '?' for x in input()]
length = len(S)

A = [0] * 13
B = [0] * 13
mod = 5
first = 0
r = 1

for i in range(length):
    a = S[length - i- 1]
    if a != '?':
        a = (a * 10 ** i) % 13
        mod -= a
        mod %= 13

    elif first == 0:
        for j in range(10):
            a = (j * 10 ** i) % 13
            A[a] += 1
        first = 1

    else:
        for j in range(10):
            a = (j * r) % 13
            for k in range(13):
                B[(k + a) % 13] += A[k]
                B[(k + a) % 13] %= 10 ** 9 + 7
        A = B
        B = [0] * 13
    r = (r * 10) % 13

print(A[mod])

Submission status: Wrong Answer

Solution code:
s = input()

# dp[k]: 13で割った余りがkのパターン数
dp = [0] * 13
mod = 10**9 + 7 
mul = 10
dp[0] = 1

for i in range(len(s)-1, -1, -1):
  nextDP = [0] * 13
  c = s[i]
#  print(c)
  if c == "?":
    for k in range(10):
      for j in range(13):
        nextDP[(j * mul + k) % 13] += dp[j]
        nextDP[(j * mul + k) % 13] %= mod
  else:
    k = int(c)
    for j in range(13):
        nextDP[(j * mul + k) % 13] += dp[j]
        nextDP[(j * mul + k) % 13] %= mod
#  mul *= 10
  dp = nextDP
print(dp[5])

Submission status: Wrong Answer

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])
        if count == 9:
            dp %= MOD
            count = 0
        else:
            count += 1
    else:
        digit += a[k] * c

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

Submission status: Wrong Answer

Solution code:
s = input()
S = []
for v in s:
    if v == '?':
        pass
    else:
        v = int(v)
    S.append(v)
length = len(S)

A = [0] * 13
B = [0] * 13
mod = 5
first = 0

for i in range(length):
    a = S[length - i- 1]
    if a != '?':
        a = (a * 10 ** i) % 13
        mod -= a
        mod %= 13
    
    elif first == 0:
        for j in range(10):
            a = (j * 10 ** i) % 13
            A[a] += 1
        first = 1

    else:
        r = (10 ** i) % 13
        for j in range(10):
            a = (j * r) % 13
            for k in range(13):
                B[(k + a) % 13] += A[k]
                B[(k + a) % 13] %= 10 ** 9 + 7
        A = B
        B = [0] * 13


print(A[mod])

Submission status: Wrong Answer

Solution code:
s = input()

# dp[k]: 13で割った余りがkのパターン数
dp = [0] * 13
mod = 10**9 + 7 
mul = 1
dp[0] = 1

for i in range(len(s)-1, -1, -1):
  nextDP = [0] * 13
  c = s[i]
#  print(c)
  if c == "?":
    for k in range(10):
      for j in range(13):
        nextDP[(j * mul + k) % 13] += dp[j]
        nextDP[(j * mul + k) % 13] %= mod
  else:
    k = int(c)
    for j in range(13):
        nextDP[(j * mul + k) % 13] += dp[j]
        nextDP[(j * mul + k) % 13] %= mod
  mul *= 10
  dp = nextDP
print(dp[5])

Submission status: Wrong Answer

Solution code:
import numpy as np
S = input()
mod = 10 ** 9 + 7

n = len(S)
dp = np.zeros((n, 13))
a = S[-1]
now, pre = 10, 1
x_ = dp[0]
if a == "?":
    x_[0:10] = 1
else:
    x_[int(a)] = 1
for s, x in zip(S[-2::-1], dp[1:]):
    if s == "?":
        x += x_
        for v in range(1, 10):
            w = 13 - v * now % 13
            x += np.hstack((x_[w:13], x_[:w]))
    else:
        v = 13 - int(s) * now % 13
        x = np.hstack((x_[v:13], x_[:v]))
    x %= mod
    now, pre = (now - pre) % 13, now
    x_ = x
print(int(dp[-1][5]))

Submission status: Wrong Answer

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

    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: Wrong Answer

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 %= MOD
print(dp[5])

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7

s = input()

cur = [0] * 13
c = s[-1]
if c != '?':
    cur[int(c)] = 1
else:
    for j in range(10):
        cur[j] = 1

d = 10
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] % mod
    cur = tmp
    d *= 10
print(cur[5])

Submission status: Wrong Answer

Solution code:
s = input()
dpa = [0]*13
dpb = [0]*13
mod = 10**9+7
lens = len(s)
flag = True

if s[-1] == '?':
  for i in range(10):
    dpa[i] += 1
else:
  dpa[int(s[-1])] += 1

for i in range(2,lens+1):
  if s[-i] == '?':
    if flag:
      for k in range(10):
        m = 10**(i-1)*k%13
        for j in range(13):
          dpb[(j+m)%13] += dpa[j]
      for l in range(13):
        dpb[l] %= mod
      dpa = [0]*13
    else:
      for k in range(10):
        m = 10**(i-1)*k%13
        for j in range(13):
          dpa[(j+m)%13] += dpb[j]
      for l in range(13):
        dpb[l] %= mod
      dpb = [0]*13
    flag = not flag          
  else:
    m = 10**(i-1)*int(s[-i])%13
    if flag:
      for j in range(13):
        dpb[(j+m)%13] = dpa[j]
      dpa = [0]*13
    else:
      for j in range(13):
        dpa[(j+m)%13] = dpb[j]
      dpb = [0]*13
    flag = not flag

print(max(dpa[5],dpb[5]))

Submission status: Wrong Answer

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)):
    multiplier = rt[10 * multiplier]
    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
  print(p[5])
main()

Submission status: Wrong Answer

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 reduces dramatically calculation time

ans = mods[5]

print(ans)

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for c in reversed(input()):
    if c == '?':
        a = list(map(sum, 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: Wrong Answer

Solution code:
s=list(input())
slen=len(s)
qs=[i for i, x in enumerate(s) if x == '?']
five=[['?']*(slen-len(list(str(i))))+list(str(i)) for i in range(1,int('9'*slen))if i%13==5]
for i in range(len(five)):
    for j in range(slen):
        if j in qs:
            five[i][j]='?'
print(five.count(s))

Submission status: Wrong Answer

Solution code:
s = input()
S = []
for v in s:
    if v == '?':
        pass
    else:
        v = int(v)
    S.append(v)
length = len(S)

A = [0] * 13
B = [0] * 13
mod = 5
first = 0

for i in range(length):
    a = S[length - i- 1]
    if a != '?':
        a = (a * 10 ** i) % 13
        mod -= a
        mod %= 13
    
    elif first == 0:
        for j in range(10):
            a = (j * 10 ** i) % 13
            A[a] += 1
        first = 1

    else:
        for j in range(10):
            a = (j * 10 ** i) % 13
            for k in range(13):
                B[(k + a) % 13] += A[k]
        for v in range(13):
            B[v] %= 10 ** 9 + 7
        A = B
        B = [0] * 13


print(A[mod])