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: Time Limit Exceeded

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)

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

    for i in range(1, len(S)):
        if S[i] == '?':
            for j in range(10):
                for r in range(13):
                    new_r = 10**(len(S) - i - 1) * j + r
                    dp[i][new_r % 13] += dp[i-1][r]

        else:
            for r in range(13):
                new_r = 10**(len(S) - i - 1) * int(S[i]) + r
                dp[i][new_r % 13] += dp[i-1][r]

    print(dp[len(S)-1][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 で実行できる

import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """??2??5"""
        output = """768"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """?44"""
        output = """1"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """7?4"""
        output = """0"""
        self.assertIO(input, output)
    def test_入力例_4(self):
        input = """?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76???"""
        output = """153716888"""
        self.assertIO(input, output)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
# for i in range(50):
#     for j in range(10):
#         print(i, ((j)*(10**i))%13)
s = s[::-1]
dp =[[0]*13 for i in range(n)]
mod0 = [[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: Time Limit Exceeded

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

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

dp[0][0]=1

q=1
for i in range(1,len(S)+1): #i文字目，1-index
  s = S[i-1]
  if s=='?':
    for j in range(13):
      for n in range(10):
      	dp[i][(j+n*q)%13] += dp[i-1][j]
    for j in range(12):
      dp[i][j] %= 10**9+7
  else:
    n = int(s)
    for j in range(13):
      dp[i][(j+n*q)%13] = dp[i-1][j]
  q = (10*q)%13
  
print(dp[len(S)][5])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from copy import deepcopy
s = input()
cnt = 0
mod_13_cnt = np.array([0]*13)
hatena = [0,1,2,3,4,5,6,7,8,9]
#定数部分を評価
s_teisu = int(s.replace("?","0")) %13
mod_13_cnt[s_teisu]+=1
fn = lambda x : x %(10**9+7)
for i,s_i in enumerate(s[::-1]):
     mod_13_cnt = np.array(list(map(fn,mod_13_cnt)))
     ph = np.array([0]*13)
     if s_i!="?":
         continue
     for j in hatena:
         add_v = j*10**i%13
         ph += np.roll(mod_13_cnt,add_v)
     mod_13_cnt = ph
print(mod_13_cnt[5]%(10**9+7))

Submission status: Time Limit Exceeded

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()
    N = len(S)
    S = reversed(S)
    dp = [[0 for j in range(13)] for i in range(N)]
 
    for i, es in enumerate(S):
        c = es
        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 * pow(10, i, 13)) % 13
                        dp[i][k] = (dp[i][k] + dp[i-1][(k-amari)%13]) % MOD
                else:
                    amari = (int(c) * pow(10, i, 13)) % 13
                    dp[i][k] += (dp[i][k] + dp[i - 1][(k-amari) % 13]) % MOD
 
    dprint(dp)
    print(dp[N-1][5])

solve()

Submission status: Time Limit Exceeded

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
    digitMask %= 13

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

count = 0
for X in itertools.product('0123456789', repeat=S.count('?')):
  s = S
  for x in X:
    s = s.replace('?', x, 1)
  if int(s) % 13 == 5:
    count = (count + 1) % A
print(count)

Submission status: Time Limit Exceeded

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)]
    dp2 = [0 for j in range(13)]

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

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

    dprint(dp)
    print(dp[5])

solve()

Submission status: Time Limit Exceeded

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

S = str(input())
n = len(S)
if n==1:
  if S=='5' or S=='?':
    print(1)
  else:
    print(0)
  exit()

dp=[[0 for j in range(13)] for i in range(n)]
for i in range(n):
  if i==0:
    if S[i]!='?':
      dp[i][int(S[i])*10**(n-1) %13] += 1
    else:
      for j in range(10):
        dp[i][j*10**(n-1) %13] += 1
  else:
    if S[i]!='?':
      for k in range(13):
        dp[i][(k+int(S[i])*10**(n-i-1))%13] += dp[i-1][k]
    else:
      for j in range(10):
        for k in range(13):
          dp[i][(k+j*10**(n-i-1))%13] += dp[i-1][k]
    for k in range(13):
      dp[i][k] %= mod
print(dp[n-1][5])

Submission status: Time Limit Exceeded

Solution code:
import math
 
s = list(map(str, input().split()))
s = s[0]
n = len(s)

now = 1
amari = []
for i in range(len(s)):
    amari.append(now)
    now = (now * 10) % 13

ans = [[0 for i in range(13)] for j in range(2)]
ans[0][0] = 1
ans[1][0] = 1

for i in range(len(s)):
    now = s[n-1-i]
    ans[(i+1)%2] = [0 for i in range(13)]
    if(now=="?"):
        for k in range(10):
            plus = (amari[i] * k)%13
            for j in range(13):
                ans[(i+1)%2][(j+plus)%13] += ans[i%2][j]
        for j in range(13):
            ans[(i+1)%2][(j+plus)%13] %= 1000000007
    else:
        now = int(now)
        plus = (amari[i] * now)%13
        for j in range(13):
            ans[(i+1)%2][(j+plus)%13] = ans[i%2][j]
            
    last = (i+1)%2
            
print(ans[last][5])

Submission status: Time Limit Exceeded

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

S_inv = S[::-1]
mod = 10**9 +7
dp = [[0] * 13 for i in range(10**6)]

dp[0][0] = 1
for i,s in enumerate(S_inv):
    keta = i%6
    if s != "?":
        for j in range(13):
            amari = (j + int(s)*10**keta)%13 #桁を追加
            dp[i+1][amari] += dp[i][j]
    else:
        for j in range(13):
            for k in range(10):
                amari = (j + k*10**keta)%13
                dp[i+1][amari] += dp[i][j]
    for j in range(13):
        dp[i+1][j] %= mod
print(dp[N][5]%mod)

Submission status: Time Limit Exceeded

Solution code:
s = ''.join(reversed(input()))
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)):
  multiplier = (10 * multiplier) % 13
  np = [0 for j in range(13)]
  if s[i] != '?':
    r = int(s[i]) * multiplier
    for j in range(13):
      np[(j + r) % 13] = p[j]
  else:
    for j in range(10):
      r = j * multiplier
      for k in range(13):
        np[(k + r) % 13] += p[k]
  for j in range(13):
    p[j] = np[j] % divisor
print(p[5] % divisor)

Submission status: Time Limit Exceeded

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のものを格納する
mod = 10 ** 9 + 7
power = 1
 
for i in range(digits):
    if s[i] == '?':
        for j in range(10):
            if i == 0:
                dp[i][j] += 1
            else:
                amari = (j * power) % 13
                for k in range(13):
                    dp[i][(k+amari)%13] = (dp[i][(k+amari)%13] + dp[i-1][k]) % mod
    else:
        val = int(s[i])
        if i == 0:
            dp[i][val] += 1
        else:
            amari = (val * power)% 13
            for k in range(13):
                dp[i][(k+amari)%13] = (dp[i][(k+amari)%13] + dp[i-1][k]) % mod
    power = (power * 10) % 13
print(dp[digits-1][5])

Submission status: Time Limit Exceeded

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:
        each_extras[cnt] = [0 for i in range(13)]
        for x in range(10):
            each_extras[cnt][x * 10 ** i % 13] = 1
        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 j in range(13):
        for e_i in range(13):
            if each_extras[i][e_i]:
                dp[i+1][(j+e_i) % 13] += dp[i][j]
    for j in range(13):
        dp[i+1][j] = dp[i+1][j] % mod

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

Submission status: Time Limit Exceeded

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

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

for i in range(length):
    if S[i] == '?':
        s = -1
    else:
        s = int(S[i])

    for j in range(10):
        if s != -1 and s != j:
            continue
        for k in range(13):
            index = (k * 10 + j) % 13
            dp[i + 1][index] = (dp[i + 1][index] + dp[i][k]) % MOD

print(dp[length][5])

Submission status: Time Limit Exceeded

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 * pow(10, i, 13)) % 13
                        dp[i][k] = (dp[i][k] + dp[i-1][(k-amari)%13]) % MOD
                else:
                    amari = (int(c) * pow(10, i, 13)) % 13
                    dp[i][k] += (dp[i][k] + dp[i - 1][(k-amari) % 13]) % MOD

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



solve()

Submission status: Time Limit Exceeded

Solution code:
s = ''.join(reversed(input()))
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)):
  multiplier = (10 * multiplier) % 13
  np = [0 for j in range(13)]
  if s[i] != '?':
    r = int(s[i]) * multiplier
    for j in range(13):
      np[(j + r) % 13] = p[j]
  else:
    for j in range(10):
      r = j * multiplier
      for k in range(13):
        np[(k + r) % 13] += p[k]
  p = np
print(p[5] % divisor)

Submission status: Time Limit Exceeded

Solution code:
import sys

def solve():
    S = input()
    mod = 7 + 10 ** 9
    DP = [[0 for _ in range(13)] for _ in range(len(S))]
    if S[0] == "?":
        for i in range(10): DP[0][i] = 1
    else: DP[0][int(S[0])] = 1

    for i in range(1, len(S)):
        if S[i] == "?":
            for j in range(13):
                for k in range(10):
                    DP[i][(j * 10 + k) % 13] += DP[i-1][j]
                    DP[i][(j * 10 + k) % 13] %= mod
        else:
            k = int(S[i])
            for j in range(13):
                DP[i][(j * 10 + k) % 13] += DP[i-1][j]
                DP[i][(j * 10 + k) % 13] %= mod
    print(DP[len(S) - 1][5])

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
s = list(input())[::-1]

mod = 10**9 + 7

rest = []
for i in range(6):
    res = []
    for j in range(10):
        res.append(((10**i)*j) % 13)
    rest.append(res)

nowtable = [0] * 13
nowtable[0] = 1

for i in range(len(s)):
    degree = i % 6
    nextable = [0] * 13
    if s[i] == '?':
        for j in range(10):
            for k in range(13):
                index = (k + rest[degree][j]) % 13
                nextable[index] = (nextable[index] + nowtable[k]) % mod
    else:
        num = int(s[i])
        for k in range(13):
            index = (k + rest[degree][num]) % 13
            nextable[index] = (nextable[index] + nowtable[k]) % mod
    nowtable = nextable

print(nowtable[5])

Submission status: Time Limit Exceeded

Solution code:
S = input()
ans = [[0] * 13 for _ in range(len(S))]
MOD = 10 ** 9 + 7
if S[0] == "?":
    for i in range(10):
        ans[0][i] = 1
else:
    ans[0][int(S[0])] = 1

for i, s in enumerate(S):
    if i == 0:
        continue
    if s == "?":
        for n in range(10):
            for j in range(13):
                ans[i][(j * 10 + n) % 13] += ans[i - 1][j]
                ans[i][(j * 10 + n) % 13] %= MOD
    else:
        for j in range(13):
            ans[i][(j * 10 + int(s)) % 13] = ans[i - 1][j]

print(ans[-1][5])

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
sosu = 10 ** 9 + 7
dp = [[0 for i in range(13)] for j in range(N)]
j = 0
if S[j] == '?':
    flag = -1
else:
    flag = int(S[j])
if flag == -1:
    for i in range(10):
        dp[j][i] += 1
else:
    dp[j][flag] = 1
#print(dp)
for j in range(1, N):
    if S[j] == '?':
        flag = -1
    else:
        flag = int(S[j])
    for k in range(10):
        if flag == -1:
            for i in range(13):
                dp[j][(i * 10 + k) % 13] += dp[j - 1][i]
            for i in range(13):
                dp[j][i] = dp[j][i] % sosu
        else:
            for i in range(13):
                dp[j][(i * 10 + flag) % 13] = dp[j-1][i]

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
S=input()
# S = "??2??5"
# S = "?44"
# S = "?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76???"
# S = "".join(["1" for _ in range(10**5)])
ROT = [1,10,9,12,3,4]
rcnt = [0 for i in range(6)]
MOD = 10**9+7
remain = 0
mod = -1
for i,ss in enumerate(S[::-1]):
  mod = (mod+1)%6
  r = ROT[mod]
  # print(ss,r)
  if ss=="?":
    rcnt[mod] += 1
  else:
    remain += int(ss)*10**i
    remain = remain%13

# print(rcnt, remain)

dp = {}

for rem in range(13):
  dp[(0,rem)] = 0
dp[(0,0)] = 1
for i in range(1,max(rcnt)+1):
  for rem in range(13):
    dp[(i, rem)] = 0
  for rem in range(13):
    for num in range(10):
      key = (i,(rem+num)%13 )
      # if key == (2,0):
      #   print(rem,num, dp[(i-1,rem)])
      dp[key] += dp[(i-1,rem)]

# print(dp)

seq = list(range(13))
am = 0
for k in itertools.product(seq,repeat=6):
  sm = 0
  for i in range(6):
    sm += k[i]*ROT[i]
  if (sm+remain)%13==5:
    cros = 1
    for i in range(6):
      cros*=dp[(rcnt[i], k[i])]
    # if cros>=1:
      # print(k, cros)
    am = (am+cros)%MOD
print(am)

Submission status: Time Limit Exceeded

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

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

for i in range(len(S)):
    if S[i] == '?':
        s = -1
    else:
        s = int(S[i])

    for j in range(10):
        if s != -1 and s != j:
            continue
        for k in range(13):
            dp[i + 1][(k * 10 + j) % 13] += dp[i][k]
            dp[i + 1][(k * 10 + j) % 13] %= MOD

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

Submission status: Time Limit Exceeded

Solution code:
"""
AtCoder
    :author: vierbein
"""
from __future__ import absolute_import, division, print_function

# import itertools as it
import collections
import sys

BIGINT = int(1e9) + 7

def pp(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)

S = input().strip()

slots = [0] * 13
slots[0] = 1

for p, c in enumerate(reversed(S)):
    xx = pow(10, p, 13)
    new_slots = [0] * 13
    if c == "?":
        for i in range(10):
            for k in range(13):
                idx = (i * xx + k) % 13
                new_slots[idx] = (new_slots[idx] + slots[k]) % BIGINT
    else:
        n = int(c)
        for k in range(13):
            new_slots[(n * xx + k) % 13] = slots[k]
    slots = new_slots

print(slots[5])

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
S = input()[::-1]
W = [1, 10, 9, 12, 3, 4]

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

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

    w = W[i % 6]
    if s == "?":
        for n in range(10):
            for j in range(13):
                r = (j + n * w) % 13
                dp[i][r] = (dp[i][r] + dp[i - 1][j]) % mod

    else:
        n = int(s)
        for j in range(13):
            r = (j + n * w) % 13
            dp[i][r] = (dp[i][r] + dp[i - 1][j]) % mod

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

Submission status: Time Limit Exceeded

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)):
  multiplier = (10 * multiplier) % 13
  np = [0 for j in range(13)]
  if s[i] != '?':
    r = (int(s[i]) * multiplier) % 13
    for j in range(len(p)):
      np[(j + r) % 13] = p[j]
  else:
    for j in range(10):
      r = (j * multiplier) % 13
      for k in range(len(p)):
        np[(k + r) % 13] += p[k]
  p = np
print(p[5] % divisor)

Submission status: Time Limit Exceeded

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

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

for i in range(len(S)):
    if S[i] == '?':
        s = -1
    else:
        s = int(S[i])

    for j in range(10):
        if s != -1 and s != j:
            continue
        for k in range(13):
            dp[i + 1][(k * 10 + j) % 13] += dp[i][k]
    for l in range(13):
        dp[i + 1][l] %= MOD

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

Submission status: Time Limit Exceeded

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][k] + dp[i-1][(k-amari)%13]) % MOD
                else:
                    amari = (int(c) * (10 ** i)) % 13
                    dp[i][k] += (dp[i][k] + dp[i - 1][(k-amari) % 13]) % MOD

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



solve()

Submission status: Time Limit Exceeded

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

S = str(input())

a = []
now = 0
for i in range(len(S)):
  if S[i]=='?':
    b = []
    for j in range(10):
      b.append((j*10**(len(S)-i-1) %13))
    a.append(b)
  else:
    now = (now+10**(len(S)-i-1)*int(S[i])) %13

if len(a)==0:
  if now==5:
    print(1)
  else:
    print(0)
  exit()

dp=[[0 for j in range(13)] for i in range(len(a))]
for i in range(len(a)):
  if i==0:
    for k in range(10):
      dp[i][(now+a[i][k])%13] = 1
  else:
    for k in range(10):
      temp = a[i][k]
      for l in range(13):
        dp[i][(l+temp)%13] += dp[i-1][l]
  for j in range(13):
    dp[i][j] = dp[i][j]%mod
print(dp[len(a)-1][5])

Submission status: Time Limit Exceeded

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][k] + dp[i-1][(k-amari)%13]) % MOD
                else:
                    amari = (int(c) * (10 ** i)) % 13
                    dp[i][k] += (dp[i][k] + dp[i - 1][(k-amari) % 13]) % MOD

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

solve()

Submission status: Time Limit Exceeded

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

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

for i, s in enumerate(S):
    if s == '?':
        s = -1
    else:
        s = int(s)

    for j in range(10):
        if s != -1 and s != j:
            continue
        for k in range(13):
            dp[i + 1][(k * 10 + j) % 13] += dp[i][k]
    for l in range(13):
        dp[i + 1][l] %= MOD

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
divisor = 1000000007
# 文字列を一文字ずつのリストに代入 test は['t', 'e', 's', 't']
s = list(input())
t = [0]*len(s)

for i in range( len(s) ):
    if s[i] == '?':
#        t.append(-1)
        t[i]=-1
    else:
#        t.append(int(s[i]))
        t[i]=int(s[i])

dp = [[0 for i in range(13)] for i in range(100005)]
dp[0][0]=1
for i in range(len(s)):
    for j in range(10):
        if t[i] == -1 or t[i] == j:
            for k in range(13):
                dp[i+1][(k*10+j)%13] += dp[i][k]
    for j in range(13):
        dp[i+1][j] = dp[i+1][j] % divisor

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

Submission status: Time Limit Exceeded

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

S = str(input())

a = []
now = 0
for i in range(len(S)):
  if S[i]=='?':
    b = []
    for j in range(10):
      b.append((j*10**(len(S)-i-1) %13))
    a.append(b)
  else:
    now = (now+10**(len(S)-i-1)*int(S[i])) %13

if len(a)==0:
  if now==5:
    print(1)
  else:
    print(0)
  exit()

dp=[[0 for j in range(13)] for i in range(len(a))]
for i in range(len(a)):
  if i==0:
    for k in range(10):
      dp[i][(now+a[i][k])%13] = 1
  else:
    for k in range(10):
      temp = a[i][k]
      for l in range(13):
        dp[i][(l+temp)%13] += dp[i-1][l]
        dp[i][(l+temp)%13] = dp[i][(l+temp)%13]%mod
print(dp[len(a)-1][5])

Submission status: Time Limit Exceeded

Solution code:
S = input()
 
ans = 0
q = [S]
while q:
    s = q.pop()
    if '?' not in s:
        if int(s) % 13 == 5:
            ans += 1
    else:
        for i in range(10):
            q.append(s.replace('?', str(i), 1))
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:

import sys

S =  sys.stdin.readline()[:-1]
l = len(S)
# S = S[::-1]
S = list(reversed(S))

dp =[[0 ] * 13 for _ in range(l + 1)]
kurai = 1
MOD = (10 ** 9) + 7
dp[0][0] = 1

for keta in range(len(S)):
    c =S[keta]

    if c == "?":
        for j in range(0,10):
            kurai %= 13
            temp = (j * kurai) % 13
            for i in range(13):
                dp[keta + 1][(temp + i) % 13] += (dp[keta][i] )
                dp[keta + 1][(temp + i) % 13] %= MOD
    else:
        kurai %= 13

        temp = (int(c) * kurai) % 13
        for i in range(13):
            dp[keta + 1][(temp + i) % 13]  += (dp[keta][i] )
            dp[keta + 1][(temp + i) % 13] %= MOD
    kurai *= 10
    keta %= MOD
print(dp[-1][5] )