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:
s=input()[::-1]
l=len(s)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1
for i in range(1,l+1):
  if s[i-1]=='?':
    for j in range(10):
      for k in range(13):
        dp[i][(k*10+j)%13]+=dp[i-1][k]%mod
  else:
    for k in range(13):
      dp[i][(k*10+int(s[i-1]))%13]+=dp[i-1][k]%mod
print(dp[-1][5]%mod)

Submission status: Wrong Answer

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

b=int(s.replace("?","0"))%13
if b<=5:
    cal=5-b
else:
    cal=18-b
d={i:0 for i in range(13)}
p=[[i*j%13 for i in range(10)] for j in range(13)]
rev=s[::-1]
num=rev.find("?")
if num==-1:
    if cal==0:
        print(1)
    else:
        print(0)
else:
    tmp=10**(num)%13
    for i in p[tmp]:
        d[i]+=1
    c=rev[num+1:]
    for i,v in enumerate(c):
        #print(i+num+1)
        if v=="?":
            tmp=10**i%13
            t_d={i:0 for i in range(13)}
            #print("i,tmp:",i+num+1,",",tmp)
            for k in range(0,13):
                for j in range(0,10):
                    t_d[(p[tmp][j]+k)%13]+=d[k]
                #print(t_d.values())
            #for j in range(13):
                #d[j]=t_d[j]
            #d=t_d
            #print(t_d)
    #print(d)
    print(d[cal]%mod)

Submission status: Wrong Answer

Solution code:
def solve(s):
    if len(s) == 1:
        return 0
    MOD = 10 ** 9 + 7
    dp = [0] * 13
    dp[0] = 1
    for c in s:
        ndp = [0] * 13
        if c == '?':
            for m, v in enumerate(dp):
                m *= 10
                for i in range(10):
                    j = (m + i) % 13
                    ndp[j] = (ndp[j] + v) % MOD
        else:
            i = int(c)
            for m, v in enumerate(dp):
                j = (m * 10 + i) % 13
                ndp[j] = (ndp[j] + v) % MOD
        dp = ndp
    return dp[5]


s = input()
print(solve(s))

Submission status: Wrong Answer

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

b=int(s.replace("?","0"))%13
if b<=5:
    cal=5-b
else:
    cal=18-b
d={i:0 for i in range(13)}
p=[[i*j%13 for i in range(10)] for j in range(13)]
rev=s
num=rev.find("?")
if num==-1:
    if cal==0:
        print(1)
    else:
        print(0)
else:
    tmp=10**(num)%13
    for i in p[tmp]:
        d[i]+=1
    c=rev[num+1:]
    for i,v in enumerate(c):
        #print(i+num+1)
        if v=="?":
            tmp=10**i%13
            t_d={i:0 for i in range(13)}
            #print("i,tmp:",i+num+1,",",tmp)
            for k in range(0,13):
                for j in range(0,10):
                    t_d[(p[tmp][j]+k)%13]+=d[k]
                #print(t_d.values())
            #for j in range(13):
                #d[j]=t_d[j]
            d=t_d
            #print(t_d)
    #print(d)
    print(d[cal]%mod)

Submission status: Wrong Answer

Solution code:

S = input()

s = list(S)

s.reverse()

#print (s)

lis = [0] * 13
lis[0] = 1
keta = 1

for i in range(len(S)):

    nlis = [0] * 13

    if s[i] == "?":

        for j in range(10):

            for k in range(13):

                nlis[ (k + (j * keta)) % 13] += lis[k]

    else:

        now = int(s[i])

        for k in range(13):

            nlis[ (k + (now * keta)) % 13 ] += lis[k]

    #print (nlis)
    keta *= 10
    for j in range(13):
        nlis[j] = lis[j]

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

Submission status: Wrong Answer

Solution code:
import numpy as np
s = input()
n = len(s)
s = s[::-1]
dp =np.array([[0]*13 for i in range(n)])
mod0 = np.array([[0,1,2,3,4,5,6,7,8,9],[0,10,7,4,1,11,8,5,2,12],[0,9,5,1,10,6,2,11,7,3],[0,12,11,10,9,8,7,6,5,4],[0,3,6,9,12,2,5,8,11,1],[0,4,8,12,3,7,11,2,6,10]])

m = 10 ** 9 + 7
if s[0] == "?":
    for i in range(10):
        dp[0,i] = 1
else:
    for i in range(10):
        dp[0,int(s[0])] = 1

for i in range(n-1):
    for j in range(13):
        mod = (i+1) % 6
        if s[i+1] == "?":
            for k in range(10):
                dp[i+1,j] += dp[i,(j-mod0[mod,k])%13]
        
        else:
            dp[i+1,j] = dp[i,(j-mod0[mod,int(s[i+1])])%13]
        dp[i,j] = dp[i,j] % m

print(dp[-1,5] % m)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import math

MOD = 1000000007  # type: int


def getarr(s):
    arr = [0] * 13
    def addmod(s):
        if s.find('?') != -1:
            for n in range(10):
                ind = s.find('?')
                scopy = s[:ind] + str(n) + s[ind+1:]
                addmod(scopy)
        else:
            suuji = int(s)
            arr[suuji % 13] += 1
    addmod(s)
    return arr


def solve(S: str):
    l = len(S)
    N = math.ceil(l / 3)
    dirction = 1

    tbl = [[0 for i in range(13)] for j in range(N)]

    for t in range(N):
        s = S[-3:]
        S = S[:-3]
        arr = getarr(s)
        if t == 0:
            tbl[t] = arr
        else:
            pasttable = tbl[t-1].copy()
            for i in range(13): # arr
                for j in range(13): # past
                    num = arr[i] * pasttable[j]
                    idx = ((j - i) * dirction) % 13
                    tbl[t][idx] += num

        dirction = dirction * -1

    print(tbl[N-1][5] % MOD)

    return

# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    S = SI()
    S = S[::-1]
    N = len(S)
    dp = [[0 for j in range(13)] for i in range(N)]

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

    dprint(dp)
    print(dp[N-1][5])



solve()

Submission status: Wrong Answer

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

S = input()
ans_mod = 10 ** 9 + 7

# 13 * 77 = 1001
# 13 * 76923 = 999999

remainder = 0
ques_counter = [0, 0, 0, 0, 0, 0]
for (i, s) in enumerate(reversed(S)):
    idx = i % 6  # 6桁区切りで何桁目？
    if s != "?":  # other than "?"
        remainder += int(s) * (10 ** idx)
    else:
        ques_counter[idx] += 1

remainder = remainder % 13

remainder_table = [0] * 13
for i in range(6):
    # i桁目についての初期条件
    if ques_counter[i] != 0:
        i_remainder_table = [[0 for x in range(13)] for x in range(ques_counter[i])]
        for j in range(10):
            idx = j * (10 ** i) % 13
            i_remainder_table[0][idx] += 1

        for j in range(1, ques_counter[i]):
            for idx in range(13):
                for n_idx in range(13):
                    i_remainder_table[j][idx] += \
                        i_remainder_table[j-1][n_idx] * i_remainder_table[0][idx - n_idx]

        if sum(remainder_table) == 0:
            remainder_table = i_remainder_table[-1]
        else:
            remainder_new_table = [0] * 13
            for idx in range(13):
                for n_idx in range(13):
                    remainder_new_table[idx] += \
                        remainder_table[n_idx] * i_remainder_table[-1][idx - n_idx] % ans_mod
            remainder_table = remainder_new_table

ans = remainder_table[5 - remainder] % ans_mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7
 
debug = True
debug = False
 
def dprint(*objects):
    if debug == True:
        print(*objects)
 
def solve():
    S = SI()
    S = S[::-1]
    N = len(S)
    dp = [[0 for j in range(13)] for i in range(N)]
 
    for i in range(N):
        c = S[i]
        if i == 0:
            if c == '?':
                for j in range(10):
                    dp[i][j] = 1
            else:
                dp[i][int(c)] = 1
        else:
            for k in range(13):
                if c == '?':
                    for j in range(10):
                        amari = (j * (10 ** i)) % 13
                        dp[i][k] += dp[i-1][(k-amari)%13]
                else:
                    amari = (int(c) * (10 ** i)) % 13
                    dp[i][k] += dp[i - 1][(k-amari) % 13]
 
    dprint(dp)
    print(dp[N-1][5])
 
 
 
solve()

Submission status: Wrong Answer

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

S = input()
ans_mod = 10 ** 9 + 7

# 13 * 77 = 1001
# 13 * 76923 = 999999

remainder = 0
ques_counter = [0, 0, 0, 0, 0, 0]
for (i, s) in enumerate(reversed(S)):
    idx = i % 6  # 6桁区切りで何桁目？
    if s != "?":  # other than "?"
        remainder += int(s) * (10 ** idx)
    else:
        ques_counter[idx] += 1

remainder = remainder % 13
print(ques_counter, remainder)

remainder_table = [0] * 13
for i in range(6):
    # i桁目についての初期条件
    if ques_counter[i] != 0:
        i_remainder_table = [[0 for x in range(13)] for x in range(ques_counter[i])]
        for j in range(10):
            idx = j * (10 ** i) % 13
            i_remainder_table[0][idx] += 1

        for j in range(1, ques_counter[i]):
            for idx in range(13):
                for n_idx in range(13):
                    i_remainder_table[j][idx] += \
                        i_remainder_table[j-1][n_idx] * i_remainder_table[0][idx - n_idx]

        if sum(remainder_table) == 0:
            remainder_table = i_remainder_table[-1]
        else:
            remainder_new_table = [0] * 13
            for idx in range(13):
                for n_idx in range(13):
                    remainder_new_table[idx] += \
                        remainder_table[n_idx] * i_remainder_table[-1][idx - n_idx] % ans_mod
            remainder_table = remainder_new_table

ans = remainder_table[5 - remainder] % ans_mod
print(ans)

Submission status: Wrong Answer

Solution code:
S = input()

MOD = 10 ** 9 + 7
MAX_LEN = len(S)
dp = [[0] * 13 for _ in range(MAX_LEN + 1)]
dp[0][0] = 1
S = S[::-1]

for i in range(MAX_LEN):
    c = int(S[i]) if S[i] != '?' else -1
    for j in range(10):
        if c != -1 and c != j:
            continue
        
        for k in range(13):
            dp[i + 1][(k * 10 + j) % 13] += dp[i][k]

        dp[i + 1][j] %= MOD
        
print(dp[-1][5])

Submission status: Wrong Answer

Solution code:
s = input()
s = [c for c in s]
s.reverse()
s = ''.join(s)
multiplier = 1
divisor = 10 ** 9 + 7
p = [0 for i in range(13)]
if s[0] != '?':
  p[int(s[0])] = 1
else:
  for j in range(10):
    p[j] = 1
for i in range(1, len(s)):
  print(','.join(map(str, p)))
  multiplier = (10 * multiplier) % 13
  if s[i] != '?':
    r = (int(s[i]) * multiplier) % 13
    np = [0 for j in range(13)]
    for j in range(len(p)):
      np[(j + r) % 13] = p[j]
    for j in range(13):
      p[j] = np[j]
  else:
    np = [0 for j in range(13)]
    for j in range(10):
      r = (j * multiplier) % 13
      for k in range(len(p)):
        np[(k + r) % 13] += p[k]
    for j in range(13):
      p[j] = np[j]
print(p[5] % divisor)

Submission status: Wrong Answer

Solution code:
S = input()

MOD = 10 ** 9 + 7
MAX_LEN = len(S)
dp = [[0] * 13 for _ in range(MAX_LEN + 1)]
dp[0][0] = 1

for i in range(MAX_LEN):
    c = int(S[i]) if S[i] != '?' else -1
    for j in range(10):
        if c != -1 and c != j:
            continue
        
        for k in range(13):
            dp[i + 1][(k * 10 + j) % 13] += dp[i][k]

        dp[i + 1][j] %= MOD
        
print(dp[-1][5])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    S = SI()
    S = S[::-1]
    N = len(S)
    dp = [[0 for j in range(13)] for i in range(N)]

    for i in range(N):
        c = S[i]
        if i == 0:
            if c == '?':
                for j in range(10):
                    dp[i][j] = 1
            else:
                dp[i][int(c)] = 1
        else:
            for k in range(13):
                if c == '?':
                    for j in range(10):
                        amari = (j * (10 ** i)) % 13
                        dp[i][k] += dp[i-1][(k-amari)%13]
                else:
                    amari = (int(c) * (10 ** i)) % 13
                    dp[i][k] += dp[i - 1][(k-amari) % 13]

    dprint(dp)
    print(dp[N-1][5])



solve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)

import re

def resolve():
    S = sys.stdin.readline().split()[0]

    logger.debug(S)
    p = re.compile(r'\?')
    q_index_list = [m.span()[0] for m in p.finditer(S)]
    logger.debug(q_index_list)

    new_s_list = list(S)
    for i in q_index_list:
        new_s_list[i] = '0'

    zero_s = int(''.join(new_s_list))

    r = (5 - (zero_s % 13)) % 13

    old_count_dict = dict(zip(range(13), [0]*13))
    old_count_dict[r] = 1

    for i in q_index_list:
        order = len(S) - i - 1

        order_mod = order % 13

        new_count_dict = dict(zip(range(13), [0]*13))

        for j in range(10):
            x = (order_mod * j) % 13
            for k in range(13):
                r = (k - x) % 13
                new_count_dict[r] += old_count_dict[k]
        
        old_count_dict = new_count_dict

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

if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

Submission status: Wrong Answer

Solution code:
arrs = list(input())
n = len(arrs)
arrs.reverse()
base = 1
arrmod = [0]*13
arrnew = [0]*13
arrmod[0] = 1

for item in arrs:
  if item == "?":
    for i in range(10):
      dif = (i*base) % 13
      for j in range(13):
        arrnew[j] += arrmod[(j+dif)%13]
  else:
    num = int(item)
    dif = (num*base) % 13
    for i in range(13):
      arrnew[i] += arrmod[(i+dif)%13]
  
  for i in range(13):
    arrmod[i] = arrnew[i] % (10**9+7)
    
  #print(arrmod)

  arrnew = [0] * 13
  base *= 10

print(arrmod[5])

Submission status: Wrong Answer

Solution code:
S = list(input())
hatena = S.count('?')
hatena_list = [len(S)-1-i for i, x in enumerate(S) if x == '?']


l = [[0]*13 for _ in range(hatena+1)]


SS = S.copy()
for i in range(len(S)):
    if SS[i] == '?':
        SS[i] = '0'
SS_13 = int(''.join(SS))%13
l[0][SS_13] = 1


def function(x):
    if x<0:
        x = 13+x
    return x



for i in range(1,hatena+1):
    s = hatena_list[i-1]
    for j in range(0,10):
        SS_13 = 10**s *j %13
        for k in range(0,13):
            l[i][k] += l[i-1][function(k-SS_13)] % 1000000007
        

print(l[-1][5])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    S = SI()
    S = S[::-1]
    N = len(S)
    dp = [[0 for j in range(13)] for i in range(N)]

    for i in range(N):
        c = S[i]
        if i == 0:
            if c == '?':
                for j in range(10):
                    dp[i][j] = 1
            else:
                dp[i][int(c)] = 1
        else:
            for k in range(13):
                if c == '?':
                    for j in range(10):
                        amari = (j * (10 ** i)) % 13
                        dp[i][k] += dp[i-1][(k+amari)%13]
                else:
                    amari = (int(c) * (10 ** i)) % 13
                    dp[i][k] += dp[i - 1][(k + amari) % 13]

    dprint(dp)
    print(dp[N-1][5])



solve()

Submission status: Wrong Answer

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

dp = [[0 for _ in range(13)] for _ in range(lenS + 1)]  # dp[digit][d] = digit桁までの mod=d の数
dp[0][0] = 1

digitMask = 1

for digit in range(1, lenS + 1) :
    if(S[-digit] == '?') :
        for d in range(13) :
            for k in range(10) :
                dp[digit][d] = (dp[digit][d] + dp[digit - 1][(d - k * digitMask) % 13]) % MOD
    else :
        a = int(S[-digit])
        for d in range(13) :
            dp[digit][d] = (dp[digit][d] + dp[digit - 1][(d - a * digitMask) % 13]) % MOD
    digitMask *= 10

ans = (dp[len(S)][5]) % MOD
print('0')

Submission status: Wrong Answer

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

a = [0] * 13
n = [0] * 13

from functools import lru_cache

@lru_cache(maxsize=10000000)
def get_base(d):
    base = 1
    for _ in range(d):
        base *= 10
        base %= 13
    return base

@lru_cache(maxsize=1000)
def get_shift(d, num):
    shift = num
    shift *= get_base(d)
    shift %= 13
    return shift

def calc(d, num):
#    shift = (num * (10 ** d))%13
    shift = get_shift(d, num)
    if d==0:
        n[shift] = 1
    else:
        for i in range(13):
            n[(i+shift)%13] += a[i]
    

for d, s in enumerate(S):
    if s=='?':
        for i in range(10):
            calc(d, i)
    else:
        calc(d, int(s[0]))
    a, n = n, a
    for i in range(13):
        a[i] %= 1000000007
        n[i] = 0

print(a[5])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)

import re

def resolve():
    S = sys.stdin.readline().split()[0]

    logger.debug(S)
    p = re.compile(r'\?')
    q_index_list = [m.span()[0] for m in p.finditer(S)]
    logger.debug(q_index_list)

    new_s_list = list(S)
    for i in q_index_list:
        new_s_list[i] = '0'

    zero_s = int(''.join(new_s_list))

    r = (5 - (zero_s % 13)) % 13

    old_count_dict = dict(zip(range(13), [0]*13))
    old_count_dict[r] = 1

    for i in q_index_list:
        order = len(S) - i - 1

        order_mod = order % 13

        new_count_dict = dict(zip(range(13), [0]*13))

        for j in range(10):
            x = (order_mod * j) % 13
            for k in range(13):
                r = (k - x) % 13
                new_count_dict[r] += old_count_dict[k]
        
        old_count_dict = new_count_dict

    print(old_count_dict[0] % (10**9 + 7))

if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

Submission status: Wrong Answer

Solution code:
S = input()

cnt = 0
i = 0
sList = list(S)
mojisu = len(S)
while (True):
    target = (13 * i) + 5

    targetList = list(str(target))
    keta = len(str(target))
    if keta > mojisu:
        break
    flag = True
    for j in range(mojisu):
        point = mojisu - j - 1
        if j + 1 <= keta:
            if sList[point] != "?" and sList[point] != targetList[keta - j - 1]:
                flag = False
                break
        else:
            if sList[point] != "?":
                flag = False
                break
    if flag:
        cnt = cnt + 1
    i = i + 1

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
#debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    S = SI()
    S = S[::-1]
    N = len(S)
    dp = [[0 for j in range(13)] for i in range(N)]

    for i in range(N):
        c = S[i]
        if i == 0:
            if c == '?':
                for j in range(9):
                    dp[i][j] = 1
            else:
                dp[i][int(c)] = 1
        else:
            for k in range(13):
                if c == '?':
                    for j in range(9):
                        amari = (j * (10 ** i)) // 13
                        dp[i][k] += dp[i-1][(k+amari)%13]
                else:
                    amari = (int(c) * (10 ** i)) // 13
                    dp[i][k] = dp[i - 1][(k + amari) % 13]

    #dprint(dp)
    print(dp[N-1][5])


solve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
#debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    S = SI()
    S = S[::-1]
    N = len(S)
    dp = [[0 for j in range(13)] for i in range(N)]

    for i in range(N):
        c = S[i]
        if i == 0:
            if c == '?':
                for j in range(9):
                    dp[i][j] = 1
            else:
                dp[i][int(c)] = 1
        else:
            for k in range(13):
                if c == '?':
                    for j in range(9):
                        amari = (j * (10 ** i)) // 13
                        dp[i][k] += dp[i-1][(k+amari)%13]
                else:
                    amari = (int(c) * (10 ** i)) // 13
                    dp[i][k] = dp[i - 1][(k + amari) % 13]

    dprint(dp)
    print(dp[N-1][5])


solve()

Submission status: Wrong Answer

Solution code:
S=input()
ans=0
MOD=10**9+7
for i in range(len(S)):
    if S[i]=='?' and len(S)-i-2>=0:
        ans+=5**(len(S)-i-2)%MOD

print(ans)

Submission status: Wrong Answer

Solution code:
S = list(input())
result = ""
fixed =[]
for i in range(len(S)):
    if S[i]=="?":
        result += "9"
    else:
        result += S[i]
        fixed.append([i,S[i]])
result = int(result)
result -= 5
# 候補
result = result //13
count = 0
for num in range(result):
    num_str = str(num)
    flag = True
    if len(num_str)<len(S):
        num_str = "0"*(len(S)-len(num_str))+num_str
    for i,si in fixed:
        if num_str[i] == str(si):
            continue
        else:
            flag = False
    if flag:
        count+=1

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

Submission status: Wrong Answer

Solution code:
S = input()

cnt = 0
i = 0
sList = list(S)
mojisu = len(S)
while (True):
    target = (13 * i) + 5
        
    targetList = list(str(target))
    keta = len(str(target))
    if keta > mojisu:
        break
    flag = True
    for j in range(mojisu):
        point = mojisu - j - 1
        if j + 1 <= keta:
            if sList[point] == "?" or sList[point] != targetList[keta - j - 1]:
                flag = False
                break
        else:
            if sList[point] != "?":
                flag = False
                break
    if flag:
        cnt = cnt + 1
    i = i + 1

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

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:
s=input()	

lis = []

for i in range(len(s)):
  if s[i].isdigit():
    lis.append(i)
cnt=0
# 文字列分だけ
for i in range(10**len(s)-1):
  x = 13 * i + 5
  if x > 10**len(s):
    break
    
  str_x = str(x).zfill(len(s))
  flag = True
  # 判明しているところだけ
  for j in range(len(lis)):
    if s[lis[j]] != str_x[lis[j]]:
      flag = False
      break
  if flag:
    cnt+=1
print(cnt/(10**9 + 7))

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 %= 13
	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:
import sys

input = sys.stdin.readline

S = input().strip()
l = len(S)
if l % 3 == 1:
    n = l // 3 + 1
    S = '00' + S
elif l % 3 == 2:
    n = l // 3 + 1
    S = '0' + S
else:
    n = l // 3
digits = [S[i * 3:(i + 1) * 3] for i in range(n)]
count1 = 1
count2 = 1
flag = False
div = 1000000007
for digit in digits[::2]:
    nq = digit.count('?')
    if nq > 0:
        flag = True

    if nq == 1:
        check = False
        for i in range(0, 10):
            s = digit
            if int(s.replace('?', str(i))) % 13 == 5:
                check = True
        if check is False:
            count1 = 0

    elif nq == 2:
        count1 *= 8

for digit in digits[1::2]:
    nq = digit.count('?')
    if nq > 0:
        flag = True

    if nq == 1:
        check = False
        for i in range(0, 10):
            s = digit
            if int(s.replace('?', str(i))) % 13 == 5:
                check = True
        if check is False:
            count2 = 0
    elif nq == 2:
        count2 *= 8

if len(digits) == 1:
    flag = False

tw = 12 if flag else 1
print((count1 * count2 * tw) % div)

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
# cleans = s.replace("?", "")

def index_Multi(List,liter):
    #Listはリスト本体・literは検索したい文字
    index_L = []
    for val in range(0,len(List)):
        if liter == List[val]:
            index_L.append(val)
    return index_L

hatena = index_Multi(s, '?')

def str_del(str,index):
    str = str[:index]+str[index+1:]
    return str

while (13*i+5 <= max):
    num = list(str(13 * i + 5))
    if(len(num) < l):
        num = ['0' for i in range(l-len(num))] + num

    for j in hatena:
        num[j] = '?'

    # flag = 1
    # for a, b in zip(s, num):
    #     if(a == '?' or a == b):
    #         continue
    #     else:
    #         flag = 0
    #         break
    # ans += flag
    if("".join(num) == s):
        ans+=1
    i += 1

print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
s = list(input())

digits = len(s)
s.reverse()
dp = [ [0] * 13 for i in range(digits)]
# dp[i][j] は i+1桁目までで13で割った余りがjのものを格納する

for i in range(digits):
    if s[i] == '?':
        for j in range(10):
            if i == 0:
                dp[i][j] += 1
            else:
                amari = ( j * 10 ** (i) ) % 13
                for k in range(13):
                    dp[i][(k+amari)%13] += dp[i-1][k]
    else:
        val = int(s[i])
        if i == 0:
            dp[i][val] += 1
        else:
            amari = ( val * 10 ** (i) ) % 13
            for k in range(13):
                dp[i][(k+amari)%13] += dp[i-1][k]
    
print(dp[digits-1][5])