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:
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

S = input()
N = len(S)
sum = 0
dp = [0] * 13
dp[0] = 1

for i, s in enumerate(S):
    n = N - i - 1
    if s == '?':
        # print("{}".format(10 ** n))
        a = [0] * 13
        for j in range(10):
            m = j * (10 ** n) % 13
            a[m] += 1

        newDP = [0] * 13
        for j1 in range(13):
            for j2 in range(13):
                newDP[(j1 + j2) % 13] += dp[j1] * a[j2]
        dp = [x % MOD for x in newDP]

    else:
        # print("{}".format(int(s) * (10 ** n)))
        sum += (int(s) * (10 ** n))
        # m2 = int(s) * (10 ** n)
        # m = (int(s) * (10 ** n)) % 13
        # dp = dp[m:] + dp[:m]

# print("sum:{}, sum%13:{}".format(sum, sum % 13))
# print(dp)
print(dp[(sum + 5) % 13])
# for i in range(13):
#     print("{:3} : {}".format(i, dp[i] % MOD))

Submission status: Wrong Answer

Solution code:
s=input()
start=int(s.replace("?","0"))
if start%13<=5:
    start+=5-start%13
else:
    start+=18-start%13
cnt=0
for i in range(start,10**(len(s)),13):
    tmp=str(i)
    for j in range(len(tmp)):
        if (not s[j]=="?") and tmp[j]!=s[j]:
            break
    else:
        cnt+=1

print(cnt%1000000007)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
mod = 10**9
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))

n = list(input())
n.reverse()
nnn = len(n)
di = 1
dp = [0 for i in range(13)]
d = [0 for i in range(13)]

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

for i in range(1,nnn):
	dp = [0 for i in range(13)]
	di *= 10
	di %= mod
	if n[i] == "?":
		for j in range(10):
			j = j * di
			j %= 13
			for kk in range(13):
				dp[(j + kk)%13] += d[kk]
				dp[(j + kk)%13] %= mod
	else:
		k = int(n[i])
		k = k * di
		k %= 13
		for kk in range(13):
			dp[(k + kk)%13] += d[kk]
			dp[(k + kk)%13] %= mod
	d = dp[:]
print(d[5]%mod)

Submission status: Wrong Answer

Solution code:
s = input()
count = []
for j in range(-1,-1*(len(s)+1),-1):
    if s[j] != "?":
        count.append(j)

ans = 0
mod = 10**9+7

t = 0
temp = ""
for i in range(76925):
    t = i * 13 + 5
    temp = 10**5 * "!" + str(t)
    if len(str(t)) > len(s):
        break
    for c in count:
        if temp[c] == "!":
            break
        if temp[c] != s[c]:
            break
    else:
        ans += 1

print(ans%mod)

Submission status: Wrong Answer

Solution code:
import functools
S = list(input())
num = [i for i, j in enumerate(S) if j == "?"]
num.sort(reverse = True)
count = 0
for n in num:
    S[n] = 0
#if "".join(S) % 13 == 5:
    #count += 1
for x in range(10):
    for n in num:
        S[n] = x
        a = int(functools.reduce(lambda x, y: x + y, [str(x) for x in S]))
        print(a)
        if a % 13 == 5:
            count += 1


print(count % (10**9 + 7))

Submission status: Wrong Answer

Solution code:
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

S = input()
N = len(S)
sum = 0
dp = [0] * 13
dp[0] = 1

for i, s in enumerate(S):
    n = N - i - 1
    if s == '?':
        # print("{}".format(10 ** n))
        a = [0] * 13
        for j in range(10):
            m = j * (10 ** n) % 13
            a[m] += 1

        newDP = [0] * 13
        for j1 in range(13):
            for j2 in range(13):
                newDP[(j1 + j2) % 13] += dp[j1] * a[j2]
        dp = [x % MOD for x in newDP]

    else:
        # print("{}".format(int(s) * (10 ** n)))
        # sum += (int(s) * (10 ** n))
        m2 = int(s) * (10 ** n)
        m = (int(s) * (10 ** n)) % 13
        dp = dp[m:] + dp[:m]

# print("sum:{}, sum%13:{}".format(sum, sum % 13))
# print(dp)
print(dp[sum])
for i in range(13):
    print("{:3} : {}".format(i, dp[i] % MOD))

Submission status: Wrong Answer

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

l = len(S)
mod = 5
box = []
for i in range(l-1, -1, -1):
    if S[l - i - 1] != '?':
        num = S[l - i - 1]
        mod -= num * 10 ** i
        mod %= 13
    else:
        num = (10 ** i) % 13
        box.append(num)



if box == []:
    print(0)
    exit()


def func(box, mod):
    length = len(box)
    if length == 1:
        ans = 0
        for i in range(10):
            if (box[0] * i) % 13 == mod % 13:
                ans += 1
        return ans
    
    else:
        a = box[-1]
        ans = 0
        for i in range(10):
            val = mod - a * i
            val %= 13
            ans += func(box[:length - 1], val)
            ans %= 10**9+7
            
        return ans


print(func(box, mod))

Submission status: Wrong Answer

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

S = input()

mod = 10 ** 9 + 7
count = S.count('?')

# stringは配列
res = []
def compute(index, string):
    if index == count or '?' not in string:
        return int(''.join(string))
    
    i = string.index('?')
    for s in range(0, 10):
        string[i] = str(s)
        item = compute(index+1, string)
        if item is not None:
            res.append(item)

compute(0, list(S))
start = 0
for item in res:
    if item % 13 == 5:
        start = item
        break
else:
    print(0)
    exit()

table = {}
for i in range(len(S)):
    if S[i] != '?':
        table[i] = int(S[i])


print((int(S.replace('?', '9')) - start) // 13)

Submission status: Wrong Answer

Solution code:
def fill(n, m):
    s = str(n)
    n = s.zfill(m)
    return(n)

S = input()

l = [5]

while l[-1] < 10**(len(S)):
    l.append(l[-1] + 13)

l = list(map(fill, l, [len(S)]*len(l)))

times = 0

for i in l:
    flag = True
    for j in range(len(S)):
        if (i[j] != S[j] and S[j] != '?'):
            flag = False
            break
    if flag == True:
        times += 1

print(times%((10**9) + 7))

Submission status: Wrong Answer

Solution code:
import sys

s = input()
h = s.count('?')
l = len(s)

if(l == 1):
    if s[0] == '?' or s[0] == '5':
        print(1)
        sys.exit()
    else:
        print(0)
        sys.exit()

max = 0

if(s[0] == '?'):
    max = 10**l
else:
    max = int(s[0]) * (10 **(l-1))


i = 0
ans = 0
while (13*i+5 <= max):
    num = str(13 * i + 5)
    if(len(num) < l):
        num = '0'*(l - len(num)) + num
    flag = 1
    for a, b in zip(s, num):
        if(a == '?' or a == b):
            continue
        else:
            flag = 0
            break
    ans += flag
    i += 1

print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
S =input()
remainder_possibility = [0] * 13
digit_remainder = 1
remainder = 0
remainder_possibility[0] = 1
for i in range(len(S)-1, -1, -1):
    if(S[i] != "?"):
        remainder += (int(S[i]) * digit_remainder) % 13
    else:
        before_possibility = remainder_possibility[:]
        remainder_possibility = [0] * 13
        for j in range(13):
            for k in range(10):
                remainder_possibility[(j+k*digit_remainder) % 13] += before_possibility[j]
                remainder_possibility[(j+k*digit_remainder) % 13] = remainder_possibility[(j+k*digit_remainder) % 13] % (10 ** 9 * 7)
    digit_remainder = (digit_remainder * 10) % 13

answer = remainder_possibility[(5 - remainder) % 13] % (10 ** 9 * 7)
print(answer)

Submission status: Wrong Answer

Solution code:
import copy
S = input()
N = len(S)
F = copy.copy(S)
Z=int(F.replace('?', '9'))
C=0
i=0
while 13*i+5 < Z:
	D=str(13*i+5)
	K=D.zfill(N)
	for j in range(N-1, -1, -1):
		if (S[j] != '?')&(S[j] != K[j]):
			break
		if j == 0:
			C+=1
	i+=1
print(C%(10**9+7))

Submission status: Wrong Answer

Solution code:
count = 0
now = 0
s = list(input())
str_len = len(s)
need_compare = [i for i in range(str_len) if s[i] != "?"]
while True:
    target = list(str(13 * now + 5))
    now += 1
    if len(target) > str_len:
        break
    for_insert = [0] * (str_len - len(target))
    target[0:0] = for_insert
    for j in need_compare:
        if s[j] != target[j]:
            break
    else:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
s = input()
keta = 10

op = [0,0,0,0,0,0,0,0,0,0,0,0,0]
np = [0,0,0,0,0,0,0,0,0,0,0,0,0]

if s[len(s)-1] == '?':
  for j in range(10):
    op[j%13] += 1
else:
  op[int(s[len(s)-1])%13]=1
#print(op)
for i in reversed(range(0, len(s)-1) ):
  myp = [0,0,0,0,0,0,0,0,0,0,0,0,0]
  np = [0,0,0,0,0,0,0,0,0,0,0,0,0]
  #print(s[i])
  
  if s[i] == '?':
    for j in range(10):
      myp[(j*keta)%13] += 1
  else:
    myp[(int(s[i])*keta)%13]=1
  #print("myp")
  #print(myp)
  for j in range(13):
    for k in range(13):
      np[(j+k)%13] += op[(j)%13]*myp[(k)%13]
      
  for j in range(13):
    op[j] = np[j]
  keta *= 10
  #print(np)
  
print(np[5] % (10**9+7))

Submission status: Wrong Answer

Solution code:
S = str(input())
keta = len(S)
max_S = int(S.replace('?', '9'))
max_i = max_S // 13

ans = 0

for i in range(max_i):
  s = str(13*i+5)
  s = s.zfill(keta)
#print(s)
#S='?0018'
  for j in range(keta):
    Ss = 1
    if S[j]==s[j] or S[j]=='?':
      Ss = 1
    else:
      Ss = 0
      break
  ans += Ss
print(ans)

Submission status: Wrong Answer

Solution code:
#code
s = input()
mod = pow(10,9) + 7
maxn = int(s.replace("?","9"))
l = len(s)
a = {}
for s0 in range(len(s)):
    if s[s0] != "?":
        a[s0] = s[s0]
n = 0
i = 0
ctr = 0
b = []
while n <= maxn:
    n = 13 * i + 5
    sn = format(n,'0'+str(l)+'d')
    flag = 0
    for k in a.keys():
        if(len(sn) > k):
            if(sn[k] != a[k]):
                flag = 1
                break
        else:
            flag = 1
    if(flag == 0):
        ctr += 1
        b.append(n)
    i += 1
    
print(ctr)

Submission status: Wrong Answer

Solution code:
S = input()
N = len(S)
DP =[0]*13
DP[0] = 1
A = 0
MOD = 10**9+7

T = [1,10,9,12,3,4]
A = 0
for i in range(N):
    A*=10
    if S[i] == "?":
        hoge = [0]*13
        for j in range(13):
            for k in range(10):
                hoge[(j+k*T[(N-i-1)%6])%13] = (hoge[(j+k*T[(N-i-1)%6])%13] + DP[j])%MOD
        DP = hoge[:]
    else:
        A += int(S[i])
    A = A%13
print(DP[(A+5)%13])

Submission status: Wrong Answer

Solution code:
#!venv/bin/python
#from collections import defaultdict 
from collections import defaultdict
from pprint import pprint
import itertools

D= 10**9 + 7
DIVISOR = 13
TARGET_REM = 5
REM = [1,10,9,12,3,4]

S = input()
RevS = S[::-1]
flexCnt = [0] * len(REM)    # of_rem
fixedSum = 0
for i in range(len(RevS)):
    s = RevS[i]
    if s == '?':
        flexCnt[i % len(REM)] += 1
    else:
        n = int(s)
        fixedSum += n * (10 ** i)


fixedRem = fixedSum % DIVISOR
FLEX_REM_TARGET = (TARGET_REM - fixedRem) % DIVISOR

flexCntSlim = []
REMSlim = []
for i in range(len(REM)):
    if flexCnt[i]:
        flexCntSlim.append(flexCnt[i])
        REMSlim.append(REM[i])

cnt = 0
ans_per_cnt = 1
if REMSlim:
    for combi in itertools.product(range(10), repeat=len(REMSlim)):
        sum = 0
        for i in range(len(REMSlim)):
            sum += combi[i] * REMSlim[i]
        if sum % DIVISOR == FLEX_REM_TARGET:
            cnt += 1
    for c in flexCntSlim:
        ans_per_cnt *= 13 ** (c - 1)
        ans_per_cnt = ans_per_cnt % D
#print(flexCnt)
#print(flexCntSlim)
#print(REMSlim)
#print(cnt)
#print(ans_per_cnt)
print((cnt * ans_per_cnt) % D)

Submission status: Wrong Answer

Solution code:
import re
S = input()

targets = []
for i in range(10**len(S) // 13):
    targets.append(i*13 + 5)
# print(targets)

regs = [S]
for i in range(len(S)-1):
    if S[i] == '?':
        regs.append(S[i+1:])
    else:
        break

# print(regs)

for i in range(len(regs)):
    regs[i] = '^' + regs[i].replace('?', '\d') + '$'
# print(regs)

ans = 0
for t in targets:
    for reg in regs:
        if re.match(reg, str(t)):
            ans += 1
            ans %= (10**9+7)
        # print(ans, t)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
mod = 10**9
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))

n = list(input())
n.reverse()
nnn = len(n)

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

if n[0] == '?':
	d = [1 for i in range(13)]
else:
	d[int(n[0])] = 1

for i in range(1,nnn):
	dp = [0 for i in range(13)]
	if n[i] == "?":
		for j in range(10):
			j = j * (10**i)
			j %= 13
			for kk in range(13):
				dp[(j + kk)%13] += d[kk]
				dp[(j + kk)%13] %= mod
	else:
		k = int(n[i])
		k = k * (10**i)
		k %= 13
		for kk in range(13):
			dp[(k + kk)%13] += d[kk]
			dp[(k + kk)%13] %= mod
	d = dp[:]
print(d[5]%mod)

Submission status: Wrong Answer

Solution code:
S =input()
remainder_possibility = [0] * 13
digit_remainder = 1
remainder = 0
remainder_possibility[0] = 1
for i in range(len(S)):
    if(S[i] != "?"):
        remainder += (int(S[i]) * digit_remainder) % 13
    else:
        before_possibility = remainder_possibility[:]
        remainder_possibility = [0] * 13
        for j in range(13):
            for k in range(10):
                remainder_possibility[(j+k*digit_remainder) % 13] += before_possibility[j]
    digit_remainder = (digit_remainder * 10) % 13


answer = remainder_possibility[(5 - remainder) % 13] % (10 ** 9 * 7)
print(answer)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

a=list(input())
while not(len(a)% 6==0):
    a.insert(0, "0")
byas=0
ans=0
f=[0,0,0,0,0,0]
ass=0
call=[0,0,0,0,0,0]#0,1,2,3,4,5, by mod 6
bas=[4,3,12,9,10,1]
for i in range(len(a)):
    if not(a[i]=="?"):
        a[i]=int(a[i])
        byas=byas+a[i]*bas[i%6]
    else:
        call[i%6]=call[i%6]+1
byas=byas%13
for f[0] in range(call[0]*9+1):
    for  f[1] in range(call[1]*9+1):
        for  f[2] in range(call[2]*9+1):
            for  f[3] in range(call[3]*9+1):
                for  f[4] in range(call[4]*9+1):
                    for  f[5] in range(call[5]*9+1):
                        ass=byas
                        for i in range(6):
                            ass=ass+f[i]*call[i]
                        if(ass)%13==5:
                            ans=ans+1
                            #print(f)
                            if(ans >(10**9+7)):
                                ans=ans-10**9+7
#print(a)
#print(byas)
#print(call)

print(ans)

Submission status: Wrong Answer

Solution code:
s = list(input())

tmp_s = ''
keta = []
for i in range(len(s)):
    if s[i] == '?':
        tmp_s += '0'
        keta.append(10 ** (len(s) - i - 1) % 13)
    else:
        tmp_s += s[i]
tmp_s = int(tmp_s)

tmp_amari = tmp_s % 13
if tmp_amari > 5:
    add_amari = 13 + 5 - tmp_amari
else:
    add_amari = 5 - tmp_amari

def shift(l, n):
    return np.array(l[n:].tolist() + l[:n].tolist())

import numpy as np
dp = np.zeros(13)
for i in range(len(keta)):
    idx = 0

    dp_new = np.zeros(13)
    for j in range(0, 10):
        if i == 0:
            dp_new[idx] = 1
        else:
            dp_new = dp_new + shift(dp, idx)
            # print(idx, shift(dp, idx))
        idx = (idx + keta[i]) % 13
    dp = dp_new % (10 ** 9 + 7)

# print(dp)

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

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
S = list(str(input()))

S.reverse()

extra = 0
each_extras = [[0 for i in range(10)] for i in range(S.count("?"))]
cnt = 0
for i in range(len(S)):
    if S[i] != "?":
        extra += int(S[i]) * 10 ** i
    else:
        for x in range(10):
            each_extras[cnt][x] = x * 10 ** i % 13
        cnt += 1

print(extra)
dp = [[0 for i in range(13)] for j in range(cnt+1)]
dp[0][extra % 13] = 1
for i in range(cnt):
    for each in each_extras[i]:
        for j in range(13):
            dp[i+1][(j + each) % 13] += dp[i][j] % mod

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

Submission status: Wrong Answer

Solution code:
S = input()

N = 10**len(S)
C = (10**9) + 7
  
def check(t):
    global S
    u = S[len(S)-len(t):]
    for i in range(len(u)):
        if u[i] != "?" and u[i] != t[i]:
            return False
    
    return True

t=5
count = 0

while t<N:
    if check(str(t)):
        count = (count+1) % C
    t+=13

print(count)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

a=list(input())
while not(len(a)% 6==0):
    a.insert(0, "0")
byas=0
ans=0
f=[0,0,0,0,0,0]
ass=0
call=[0,0,0,0,0,0]#0,1,2,3,4,5, by mod 6
bas=[4,3,12,9,10,1]
for i in range(len(a)):
    if not(a[i]=="?"):
        a[i]=int(a[i])
        byas=byas+a[i]*bas[i%6]
    else:
        call[i%6]=call[i%6]+1
byas=byas%13
for f[0] in range(call[0]*9+1):
    for  f[1] in range(call[1]*9+1):
        for  f[2] in range(call[2]*9+1):
            for  f[3] in range(call[3]*9+1):
                for  f[4] in range(call[4]*9+1):
                    for  f[5] in range(call[5]*9+1):
                        ass=0
                        for i in range(6):
                            ass=ass+f[i]*call[i]
                        if(ass+byas)%13==5:
                            ans=ans+1
                            print(f)
                            if(ans >(10**9+7)):
                                ans=ans-10**9+7
#print(a)
#print(byas)
#print(call)

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    ans = 0
    s = str(input())
    sLen = len(s)
    qCount = s.count("?")
    ss = []
    for i in range(10 ** qCount):
        sss = s
        n = i
        for j in range(qCount):
            sss = QuestionReplace(sss, n % 10)
            n //= 10
        ss.append(sss)

    for i in ss:
        if bl(i):
            ans += 1
    print(ans % (10**9 + 7))


def QuestionReplace(s, n):
    return s.replace("?", str(n), 1)


def bl(n):
    nstr = str(n)
    if len(nstr) % 3 == 2:
        nstr = "0" + nstr
    elif len(nstr) % 3 == 1:
        nstr = "00" + nstr
    nlist = [int(nstr[i: i + 3]) for i in range(0, len(nstr), 3)]
    diff = abs(sum(nlist[0::2]) - sum(nlist[1::2]))
    return diff % 13 == 5


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
S = input()
N = len(S)
DP =[0]*13
DP[0] = 1
A = 0
MOD = 10**9+7

B = [[0]*13 for i in range(13)]
for i in range(13):
    for j in range(13):
        B[i][j] = (i*j)%13
T = [1,10,9,12,3,4]
A = 0
for i in range(N):
    A*=10
    if S[i] == "?":
        hoge = [0]*13
        for j in range(13):
            for k in range(10):
                hoge[(j+k*T[(N-i-1)%6])%13] = (hoge[(j+k*T[(N-i-1)%6])%13] + DP[j])%MOD
        DP = hoge[:]
    else:
        A = (A+int(S[i]))%13
print(DP[(A+5)%13])

Submission status: Wrong Answer

Solution code:
s=list(input())
s.reverse()
l=[1,10,9,12,3,4]
p=10**9+7
dp=[[0 for i in range(13)] for j in range(len(s))]
if s[0]=='?':
  for i in range(9):
    dp[0][i]+=1
else:
  dp[0][int(s[0])]+=1
for i in range(1,len(s)):
  if s[i]!='?':
    for j in range(13):
      dp[i][j]+=dp[i-1][j-(int(s[i])*l[i%6])%13]
      dp[i][j]%=p
  else:
    for j in range(13):
      for k in range(10):
        dp[i][j]+=dp[i-1][(j-k*l[i%6])%13]
        dp[i][j]%=p
print(dp[len(s)-1][5])

Submission status: Wrong Answer

Solution code:
import copy
S = input()
N = len(S)

S2 = []
for k in range(N):
    S2.append(S[k])

T = copy.copy(S2)
for i in range(N):
    if T[i] == "?":
        T[i] = "9"

T2 = ''.join(T)

T2 = int(T2)
M = T2//13 #整数部分

ans = 0

for j in range(M):
    S3 = copy.copy(S2)
    Q = 13*j+5 #比較
    Q = str(Q)
    q = len(Q)
    Q2 = [0 for u in range(N)]
    for p in range(q):
        Q2[-p-1] = Q[-p-1]
    
    
    for i in range(N):
        if S3[i] == "?":
            S3[i] = Q2[i]
    
    
    if S3 == Q2:
        ans += 1

ans = ans%(10**9+7)

print(ans)

Submission status: Wrong Answer

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

s = input()
digits = len(s)

cnt = 0
for i, c in enumerate(reversed(s)):
    if c == '?':
        continue
    n = int(c) * pow(10, i, 13) % 13
    cnt += n
print(cnt)

before = [0] * 13
first_time = True
for i, c in enumerate(reversed(s)):
    if c != '?':
        continue
    if first_time:
        for j in range(10):
            n = j * pow(10, i, 13) % 13
            before[n] += 1
        first_time = False
        continue
    current = [0] * 13
    for j in range(10):
        n = j * pow(10, i, 13) % 13
        current[n] += 1
    after = [0] * 13
    for j in range(13):
        for k in range(13):
            after[j] += before[k] * current[(13 - k + j) % 13]
        after[j] %= MOD
    before = after

if first_time:
    if cnt % 13 == 5:
        print(1)
    else:
        print(0)
else:
    print(before[(5 - (cnt % 13)) % 13])

Submission status: Wrong Answer

Solution code:
s = input()
n = len(s)

cnt = 0 

for i in range(10**n//13):
  num = str(13*i+5)
  num = "0" * (n -len(num)) + num
  flag = True
  for i,v in enumerate(s):
    if v!="?" and str(num)[i] != v:
      flag = False
  if (flag):
    cnt+=1
    
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict

def main():
    data_num = input()
    data = list(data_num)
    # data = input()
    mod = 10 ** 9 + 7

    q_num = data.count('?')

    kari = 0
    for i in range(len(data) - 1):
        if data[i + 1] != '?' and data[i] == '?':
            kari += 1


    ans = pow(10, q_num)
    ans //= 13

    # print(kari, ans)

    if data[-1] == '?':
        ans += kari
    else:
        ans -= kari - 1

    if q_num == 0:
        if int(data_num) % 13 == 5:
            ans = 1
        else:
            ans = 0
    elif q_num == 1:
        ans = 0
        for i in range(10):
            bbb = data_num.replace('?', str(i))
            if int(bbb) % 13 == 5:
                ans += 1

    print(ans % mod)







if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
S=list(input())
max_word=10**(len(S))
max_word=max_word-max_word%13+5
sum=0
ans=0
for i in range(len(S)):
  if S[i]=='?':
    S[i]=='10'
    sum+=1
while(1):
  count=0
  box=list(str(max_word))
  if max_word<=0:
    break
  while(1):
    if len(box)!=len(S):
      box.insert(0,'10')
    else:
      break
  for i in range(len(S)):
    if S[i] != box[i]:
      count+=1
  if sum==count:
    ans+=1
  max_word-=13
print(ans)

Submission status: Wrong Answer

Solution code:
S = input().strip()

a = 130
for i in range(100000):
    b = a % 13

print(a)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
def solve(A):
    N = len(A)
    dp = [1] + [0] * 12
    pwr = 1
    for i in xrange(N-1, -1, -1):
        if A[i] == '?':
            dp2 = [0] * 13
            for k, v in enumerate(dp):
                for d in xrange(10):
                    k2 = (k + d * pwr) % 13
                    dp2[k2] += v
                    dp2[k2] %= MOD
            dp = dp2
        else:
            shift = int(A[i]) * pwr % 13
            dp = dp[:shift] + dp[shift:]

        pwr *= 10
        pwr %= 13
    return dp[5] % MOD
        
print solve(raw_input().rstrip())

Submission status: Wrong Answer

Solution code:
def inpl(): return list(map(int, input().split()))

MOD = 10**9 + 7
S = input()[::-1]
x = 1

DP = [0]*13
DP[0] = 1
for i in range(len(S)):
    DP2 = [0]*13
    if S[i] != "?":
        s = int(S[i])
        for i in range(13):
            DP2[(i + s*x)%13] = DP[i]%MOD
    else:
        for j in range(10):
            for i in range(13):
                DP2[(i + j*x)%13] = (DP2[(i + j*x)%13] + DP[i])%MOD
    x = x*10%MOD
    DP = DP2

print(DP[5]%MOD)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import deque
import itertools
from itertools import permutations
import sys
import bisect
sys.setrecursionlimit(10**6)
#input=sys.stdin.readline
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
YNeos='YNeos'
mo=10**9+7
imp='IMPOSSIBLE'


s=input()
t=list(s)[::-1]
ans=0
dp=[0]*13
dp[0]=1
for d in range(len(t)):
    
    if t[d]=='?':
        tm=[0]*13
        for x in range(10):
            r=int(x)*pow(10,d,mo)
            for i in range(13):
                tm[(i+r)%13]+=dp[i]
        dp=[j%mo for j in tm]
    else:
        tm=[0]*13
        r=int(t[d])*pow(10,d,mo)
        for i in range(13):
            tm[(i+r)%13]=dp[i]
        dp=[j for j in tm]
    #print(dp)

print(dp[5]%mo)

Submission status: Wrong Answer

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

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

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

print(dp[-1][5])

Submission status: Wrong Answer

Solution code:
s = input()[::-1]
m = 13
mod = 10**9+7

r = [1]
for i in range(10**5):
    r.append(r[-1]*10 % mod)

dp = [0]*m
dp[0] = 1
for i, c in enumerate(s):
    nxt = [0]*m
    if c == "?":
        for j in range(m):
            for k in range(10):
                nxt[(j+k*r[i])%m] += dp[j]
                nxt[(j+k*r[i])%m] %= mod
    else:
        n = int(c)
        for j in range(m):
            nxt[(j+n*r[i])%m] += dp[j]
            nxt[(j+n*r[i])%m] %= mod
    dp = nxt
print(dp[5])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 1000000007  # type: int


def solve(S: str):
    dp = [0]*13
    dp[0] = 1
    dpn = [0]*13
    keta = 1
    for c in reversed(S):
        if c == "?":
            dpn = [0]*13
            for i in range(10):
                for j in range(13):
                    dpn[j] += dp[(j + i*keta) % 13]
                    dpn[j] %= MOD
            dp = dpn
        else:
            shift = (int(c)*keta) % 13
            dpn = dp[shift:] + dp[:shift]
            dp = dpn

        # print(c, dp)
        keta *= 10
        keta %= 13

    print(dp[5])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
s = input()
a = [0] * 13
a[0] = 1
for c in s:
  b = [0] * 13
  if c == '?':
    for i in range(13):
      for j in range(10):
        k = (i * 10 + j) % 13
        b[k] += a[i]
  else:
    j = ord(c) - ord('0')
    for i in range(13):
      k = (i * 10 + j) % 13
      b[k] += a[i]
  a = b
print(a[5])

Submission status: Wrong Answer

Solution code:
def find(S):
    MOD=10**9+7
    S=S[::-1]
    dp=[[0]*13 for i in range(len(S))]
    power=1
    if S[0]=="?":
        for i in range(10):
            dp[0][i]=1
    else:
        dp[0][int(S[0])]=1
    
    for i in range(1,len(S)):
        power*=10
        power%=13
        if S[i]=="?":
            for j in range(13):
                for k in range(10):
                    dp[i][j]+=dp[i-1][(j-power*k)%13]
                    dp[i][j]%=MOD
        else:
            for j in range(13):
                k=int(S[i])
                dp[i][j]+=dp[i-1][(j-power*k)%13]
                dp[i][j]%=MOD              
    return dp[-1][5]

Submission status: Time Limit Exceeded

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

s = input().rstrip()[::-1]
DP=[0 for _ in range(13)]

DP[0]=1
m = 10**9+7
mul = 1
for i in range(len(s)):
    dig = s[i]
    nextDP = [0 for _ in range(13)]
    if dig == '?':
        for j in range(10):
            for k in range(13):
                nextDP[(k+mul*j)%13] += DP[k]
                nextDP[(k+mul*j)%13]%=m
    else:
        j = int(dig)
        for k in range(13):
            nextDP[(k+mul*j)%13] += DP[k]
            nextDP[(k+mul*j)%13]%=m

    mul *= 10
    mul%=13
    DP = nextDP

print(DP[5]%m)

Submission status: Time Limit Exceeded

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

s = input().rstrip()[::-1]
DP=[0 for _ in range(13)]

DP[0]=1
m = 10**9+7
mul = 1
for i in range(len(s)):
    dig = s[i]
    nextDP = [0 for _ in range(13)]
    if dig == '?':
        for j in range(10):
            for k in range(13):
                nextDP[(k+mul*j)%13] += DP[k]
                nextDP[(k+mul*j)%13]%=m
    else:
        j = int(dig)
        for k in range(13):
            nextDP[(k+mul*j)%13] += DP[k]
            nextDP[(k+mul*j)%13]%=m

    mul *= 10
    DP = nextDP

print(DP[5]%m)