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:
d=[0]*13
d[0]=1
mul=1
mulmod=1
t=input()[::-1]

zero=[0]*13
l=len(t)
modlist=[10**i%13 for i in range(l)]
for n,c in enumerate(t):
    e=zero[:]

    for i in (range(10) if c=="?" else[int(c)]):
        for j in range(13):
            #e[(i*mul+j)%13]+=d[j]
            k=(i*modlist[n]+j)%13
            e[k]+=d[j]
            e[k]%=1000000007
    d,e=e,d
    mul*=10
    #mulmod=mul%13
print(d[5])

Submission status: Time Limit Exceeded

Solution code:

d=[0]*13
d[0]=1
mul=1
mulmod=1
t=list(input())
t.reverse()
zero=[0]*13
l=len(t)
modlist=[10**i%13 for i in range(l)]
for n,c in enumerate(t):
    e=zero[:]

    for i in (range(10) if c=="?" else[int(c)]):
        for j in range(13):
            #e[(i*mul+j)%13]+=d[j]
            k=(i*modlist[n]+j)%13
            e[k]+=d[j]
            e[k]%=1000000007
    d,e=e,d
    mul*=10
    #mulmod=mul%13
print(d[5])

Submission status: Time Limit Exceeded

Solution code:
s = input()

dp = [[0 for i in range(13)] for j in range(len(s))]
mod = 10 ** 9 + 7

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

    else:
        if s_i == "?":
            for k1 in range(10):
                for k2 in range(13):
                    dp[i][(k2 * 10 + k1) % 13] += dp[i-1][k2] % mod

        else:
            for k in range(13):
                dp[i][(k*10+int(s_i))%13] += dp[i-1][k] % mod


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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
MAX = 10**5+5
INF = 10**9
P = 1000000007

def resolve():
    s = input().strip()
    dp = [[0]*13 for _ in range(MAX)]
    dp[0][0]=1
    for i,x in enumerate(s):
        if x=='?':
            c=-1
        else:
            c=int(x)
        for j in range(10):
            if(c!=-1 and c!=j):
                continue
            for k in range(13):
                t=(k*10+j)%13
                dp[i+1][t] = dp[i+1][t]+dp[i][k]
    l=len(s)
    print(dp[l][5]%P)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
d=[0]*13
d[0]=1
mul=1
mulmod=1
t=list(input())
t.reverse()
zero=[0]*13
for c in t:
    e=zero[:]

    for i in (range(10) if c=="?" else[int(c)]):
        for j in range(13):
            #e[(i*mul+j)%13]+=d[j]
            k=(i*mul+j)%13
            e[k]+=d[j]
            e[k]%=1000000007
    d,e=e,d
    mul*=10
    #mulmod=mul%13
print(d[5])

Submission status: Time Limit Exceeded

Solution code:
d=[0]*13
d[0]=1
mul=1
mulmod=1
t=list(input())
t.reverse()
zero=[0]*13
for c in t:
    e=zero[:]

    for i in (range(10) if c=="?" else[int(c)]):
        for j in range(13):
            #e[(i*mul+j)%13]+=d[j]
            k=(i*mulmod+j)%13
            e[k]+=d[j]
            e[k]%=1000000007
    d=e[:]
    mul*=10
    mulmod=mul%13
print(d[5])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
MAX = 10**5+5
INF = 10**9
P = 1000000007

def resolve():
    s = input().strip()
    dp = [[0]*13 for _ in range(MAX)]
    dp[0][0]=1
    for i,x in enumerate(s):
        c=ord(x)-48
        for j in range(10):
            if(x!='?' and c!=j):
                continue
            for k in range(13):
                t=(k*10+j)%13
                dp[i+1][t] = dp[i+1][t]+dp[i][k]
        for j in range(10):
            dp[i+1][j]=dp[i+1][j]%P
    l=len(s)
    print(dp[l][5])


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
d=[0]*13
d[0]=1
mul=1
mulmod=1
t=list(input())
t.reverse()
zero=[0]*13
for c in t:
    e=zero[:]

    for i in (range(10) if c=="?" else[int(c)]):
        for j in range(13):
            #e[(i*mul+j)%13]+=d[j]
            e[(i*mulmod+j)%13]+=d[j]
            
    d=[e%(10**9+7)for e in e]
    mul*=10
    mulmod=mul%13
print(d[5])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
import numpy as np

def main():
    S = input()
    
    lenS = len(S)
    N = 13
    DP = np.zeros(N, dtype=np.int64)
    DP[0] = 1
    
    mod = 10 ** 9 + 7
    mul = 1
    for i in reversed(range(lenS)):
        nextDP = np.zeros(N, dtype=np.int64)
        c = S[i]
        if c == '?':
            for k in range(10):
                for j in range(N):
                    nextDP[(k * mul + j) %N] += DP[j]
                    nextDP[(k * mul + j) %N] %= mod

        else:
            k = int(S[i])
            for j in range(N):
                nextDP[(k * mul + j) %N] += DP[j]
                nextDP[(k * mul + j) %N] %= mod

        mul *= 10
        mul %= N
        DP = nextDP

    return DP[5]

if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

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

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

print(dp[N][5] % mod)

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

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

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

    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:
INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for j in range(13):
            for k in range(10):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        for j in range(13):
            dp[i + 1][(mul * int(x) + j) % 13] += dp[i][j]
            dp[i + 1][(mul * int(x) + j) % 13] %= INF
    mul *= 10

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

Submission status: Time Limit Exceeded

Solution code:
INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    for j in range(13):
        if S[-(i + 1)] == "?":
            for c in range(10):  # cはi+1番目の桁の値
                dp[i + 1][(mul * c + j) % 13] += dp[i][j]
        else:
            c = int(S[-(i + 1)])  # cはi+1番目の桁の値
            dp[i + 1][(mul * c + j) % 13] += dp[i][j]
    mul *= 10

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

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

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

        else:
            for r in range(13):
                new_r = order_r * 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:
M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for c in reversed(input()):
    r = range(0, p * 10, p) if c == '?' else (p * int(c),)
    a = [sum(a[(i - j) % 13] for j in r) % M for i in range(13)]
    p = p * 10 % 13
print(a[5])

Submission status: Time Limit Exceeded

Solution code:
s=input()
mod=10**9+7
dp = [[0]*15 for i in range(100005)]
dp[0][0]=1
for i in range(len(s)):
    keta = len(s)-i-1

    if s[i]=='?':
        nums = range(10)
    else:
        nums = [int(s[i])]
    
    tmp = pow(10,keta,13)
    for num in nums:
        amari = num*tmp%13
        for j in range(13):
            dp[i+1][(j+amari)%13]+=dp[i][j]
            dp[i+1][(j+amari)%13]%=mod

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

Submission status: Time Limit Exceeded

Solution code:
s=input()
mod=10**9+7
dp = [[0]*15 for i in range(100005)]
dp[0][0]=1
for i in range(len(s)):
    keta = len(s)-i-1

    if s[i]=='?':
        nums = range(10)
    else:
        nums = [int(s[i])]
    
    tmp = 10**keta%13
    for num in nums:
        amari = num*tmp%13
        for j in range(13):
            dp[i+1][(j+amari)%13]+=dp[i][j]
            dp[i+1][(j+amari)%13]%=mod

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

Submission status: Time Limit Exceeded

Solution code:
M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for c in reversed(input()):
    r = range(10) if c == '?' else (int(c),)
    a = [sum(a[(i - p * j) % 13] for j in r) % M for i in range(13)]
    p = p * 10 % 13
print(a[5])

Submission status: Time Limit Exceeded

Solution code:
def INT_(n): return int(n)-1
def MI(): return map(int, input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_, input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n: int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split())) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
MOD = 10**9 + 7

import numpy as np

pow_mods = [1, 10, 9, 12, 3, 4]


def main():
    S = input()
    length = len(S)
    dp = np.zeros((length, 13), dtype=np.int64)
    # dp = [[0] * 13 for _ in range(length)]
    for idx, s in enumerate(S[::-1]):
        # power = length - idx - 1
        power = idx
        if s == '?':
            table = get_table(power)
            if idx == 0:
                for mod in table:
                    dp[idx, mod] += 1
                continue
            for mod in table:
                for j in range(13):
                    dp[idx, (j + mod) % 13] += dp[idx - 1, j] % MOD
        else:
            mod = (int(s) * pow_mods[power % 6]) % 13
            if idx == 0:
                dp[idx, mod] = 1
                continue
            for j in range(13):
                dp[idx, (j + mod) % 13] += dp[idx - 1, j] % MOD

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


def get_table(n):
    return [(i * pow_mods[n % 6]) % 13 for i in range(10)]


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s=input()
mod=10**9+7
ans=0
dp = [[0]*15 for i in range(100005)]
dp[0][0]=1
for i in range(len(s)):
    keta = len(s)-i-1
    if s[i]=='?':
        for num in range(10):
            amari = num*10**keta
            amari%=13
            for j in range(13):
                dp[i+1][(j+amari)%13]+=dp[i][j]
                dp[i+1][(j+amari)%13]%=mod
    else:
        amari = int(s[i])*10**keta
        amari%=13
        for j in range(13):
            dp[i+1][(j+amari)%13]+=dp[i][j]
            dp[i+1][(j+amari)%13]%=mod

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

Submission status: Time Limit Exceeded

Solution code:
S = input()

T = [s if s != "?" else "0" for s in S]
T = int(''.join(T))
SS = T % 13

c = {}
for i in range(len(S)):
    if S[len(S) - i - 1] != "?":
        continue
    tc = {i: 0 for i in range(13)}
    for j in range(0, 10):
        t = j * 10 ** i
        tc[t % 13] += 1
    c[i] = tc

dp = []
tdp = {i: 0 for i in range(13)}
tdp[SS] += 1
dp.append(tdp)
for k, v in c.items():
    tdp = {i: 0 for i in range(13)}
    for r, c in v.items():
        for _r, _v in dp[-1].items():
            tdp[(_r + r) % 13] += _v * c
    dp.append(tdp)

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

Submission status: Time Limit Exceeded

Solution code:

d=[0]*13
d[0]=1
mul=1
t=list(input())
t.reverse()
for c in t:
    e=[0]*13
    """
    if c=="?":
        for i in range(10):
            for j in range(13):
                e[(i*mul+j)%13]+=d[j]
                e[(i*mul+j)%13]%=(10**9+7)
    else:
        for j in range(13):
            e[(int(c)*mul+j)%13]+=d[j]
            e[(int(c)*mul+j)%13]%=(10**9+7)
    """
    for i in (range(10) if c=="?" else[int(c)]):
        for j in range(13):
            e[(i*mul+j)%13]+=d[j]
            
    d=[e%(10**9+7)for e in e]
    mul*=10
print(d[5])

Submission status: Time Limit Exceeded

Solution code:

d=[0]*13
d[0]=1
mul=1
t=reversed(input())
for c in t:
    e=[0]*13
    """
    if c=="?":
        for i in range(10):
            for j in range(13):
                e[(i*mul+j)%13]+=d[j]
                e[(i*mul+j)%13]%=(10**9+7)
    else:
        for j in range(13):
            e[(int(c)*mul+j)%13]+=d[j]
            e[(int(c)*mul+j)%13]%=(10**9+7)
    """
    for i in (range(10) if c=="?" else[int(c)]):
        for j in range(13):
            e[(i*mul+j)%13]+=d[j]
            
    d=[e%(10**9+7)for e in e]
    mul*=10
print(d[5])

Submission status: Time Limit Exceeded

Solution code:

d=[0]*13
d[0]=1
mul=1
for c in reversed(input()):
    e=[0]*13
    """
    if c=="?":
        for i in range(10):
            for j in range(13):
                e[(i*mul+j)%13]+=d[j]
                e[(i*mul+j)%13]%=(10**9+7)
    else:
        for j in range(13):
            e[(int(c)*mul+j)%13]+=d[j]
            e[(int(c)*mul+j)%13]%=(10**9+7)
    """
    for i in (range(10) if c=="?" else[int(c)]):
        for j in range(13):
            e[(i*mul+j)%13]+=d[j]
            
    d=[e%(10**9+7)for e in e]
    mul*=10
print(d[5])

Submission status: Time Limit Exceeded

Solution code:
d=[0]*13
d[0]=1
mul=1
for c in reversed(input()):
    e=[0]*13
    """
    if c=="?":
        for i in range(10):
            for j in range(13):
                e[(i*mul+j)%13]+=d[j]
                e[(i*mul+j)%13]%=(10**9+7)
    else:
        for j in range(13):
            e[(int(c)*mul+j)%13]+=d[j]
            e[(int(c)*mul+j)%13]%=(10**9+7)
    """
    for i in (range(10) if c=="?" else[int(c)]):
        for j in range(13):
            e[(i*mul+j)%13]+=d[j]
            e[(i*mul+j)%13]%=(10**9+7)    
    d=e[:]
    mul*=10
print(d[5])

Submission status: Time Limit Exceeded

Solution code:

d=[0]*13
d[0]=1
mul=1
for c in reversed(input()):
    e=[0]*13
    if c=="?":
        for i in range(10):
            for j in range(13):
                e[(i*mul+j)%13]+=d[j]
                e[(i*mul+j)%13]%=(10**9+7)
    else:
        for j in range(13):
            e[(int(c)*mul+j)%13]+=d[j]
            e[(int(c)*mul+j)%13]%=(10**9+7)
    d=e[:]
    mul*=10
print(d[5])

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
s = input()
n = len(s)
dp = [0 for _ in range(13)]
dp[0] = 1
for i in range(n):
	dpp = [0 for _ in range(13)]
	if s[i] != "?":
		for j in range(13):
			dpp[(j*10+int(s[i])) % 13] = dp[j]
	else:
		for j in range(13):
			for k in range(10):
				dpp[(j*10+k)%13] += dp[j]
				dpp[(j*10+k)%13] %= MOD
	dp = dpp
print(dp[5])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
s = input()[::-1]
n = len(s)
dp = [0 for _ in range(13)]
dp[0] = 1
for i in range(n):
	dpp = [0 for _ in range(13)]
	if s[i] != "?":
		for j in range(13):
			dpp[(j + (10**i)*int(s[i])) % 13] = dp[j]
	else:
		for j in range(13):
			for k in range(10):
				dpp[(j + (10**i)*k) % 13] += dp[j]
	dp = [dppp%MOD for dppp in dpp]
print(dp[5])

Submission status: Time Limit Exceeded

Solution code:

S = input()
mod = 10**9+7
N = len(S)

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

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

print(dp[N][5])

Submission status: Time Limit Exceeded

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

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

if invs[0]=='?':
    for i in range(10): # 0~9までは1 10~12は0のまま
        dp[0][i] = 1
else:
    dp[0][int(invs[0])] = 1

mul = 10
for order in range(1,len(s)):
    for j in range(13):
        if invs[order] == '?':
            for number in range(10):
                dp[order][ (j+number * mul )%13  ]  += dp[order-1][j]%MOD
        else:
            number = int(invs[order])
            dp[order][(j+number * mul )%13 ]  += dp[order-1][j]%MOD
        dp[order][(j+number * mul )%13 ] %= MOD
    mul *= 10
    mul %= 13
print(dp[-1][5]%MOD)

Submission status: Time Limit Exceeded

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

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

if invs[0]=='?':
    for i in range(10): # 0~9までは1 10~12は0のまま
        dp[0][i] = 1
else:
    dp[0][int(invs[0])] = 1

for order in range(1,len(s)):
    for j in range(13):
        if invs[order] == '?':
            for number in range(10):
                dp[order][ (j+number * (10**order)%13 )%13  ]  += dp[order-1][j]%MOD
        else:
            number = int(invs[order])
            dp[order][(j+number * (10**order)%13 )%13 ]  += dp[order-1][j]%MOD
        dp[order][(j+number * (10**order)%13 )%13 ] %= MOD
 
print(dp[-1][5]%MOD)

Submission status: Time Limit Exceeded

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

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

if invs[0]=='?':
    for i in range(10): # 0~9までは1 10~12は0のまま
        dp[0][i] = 1
else:
    dp[0][int(invs[0])] = 1

for order in range(1,len(s)):
    for j in range(13):
        if invs[order] == '?':
            for number in range(10):
                dp[order][ (j+number * 10**order)%13  ]  += dp[order-1][j]%MOD
        else:
            number = int(invs[order])
            dp[order][(j+number * 10**order)%13 ]  += dp[order-1][j]%MOD
        dp[order][(j+number * 10**order)%13 ] %= MOD
 
print(dp[-1][5]%MOD)

Submission status: Time Limit Exceeded

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

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

if invs[0]=='?':
    for i in range(10): # 0~9までは1 10~12は0のまま
        dp[0][i] = 1
else:
    dp[0][int(invs[0])] = 1

for order in range(1,len(s)):
    for j in range(13):
        if invs[order] == '?':
            for number in range(10):
                dp[order][ (j+number * 10**order)%13  ]  += dp[order-1][j]%MOD
        else:
            number = int(invs[order])
            dp[order][(j+number * 10**order)%13 ]  += dp[order-1][j]%MOD
 
print(dp[-1][5]%MOD)

Submission status: Time Limit Exceeded

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

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

for i, s in enumerate(S):
    if s == '?':
        c = -1
    else:
        c = int(s)
    
    for j in range(10):
        if c != -1 and c != j:
            continue
        
        for n in range(13):
            dp[i + 1][(n * 10 + j) % 13] += dp[i][n]
        
        for m in range(13):
            dp[i + 1][m] %= MOD

print(dp[l][5])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys

s = sys.stdin.readline().strip()

MOD = 10 ** 9 + 7
mmap = []
for i in range(6):
    b = 10 ** i % 13
    mmap.append([[(b * i + j) % 13 for i in range(1,10)] for j in range(13)])

dp = [0] * 13
dp[0] = 1
j = 0
for c in reversed(s):
    tmp = dp.copy()

    if c == "0":
        pass
    elif c == "?":
        bset = mmap[j]
        for m, num in enumerate(tmp):
            if num == 0:
                continue
            for idx in bset[m]:
                dp[idx] += num
        
        for i in range(13):
            dp[i] %= MOD
    else:
        b = mmap[j][0][int(c) - 1]
        for n in range(13):
            idx = (n + b) % 13
            dp[idx] = tmp[n]
    
    if j==5:
        j = 0
    else:
        j+=1

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

S = input()
N = len(S)

dp = [[0 for _ in range(13)] for _ in range(N + 5)]
dp[0][0] = 1

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

    for j in range(10):
        if c != -1 and c != j:
            continue

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

        for r in range(13):
            dp[i + 1][r] %= MOD

print(dp[N][5])

Submission status: Time Limit Exceeded

Solution code:
# D
import numpy as np
S = input()
N = len(S)
dp = [[0 for i in range(13)] for j in range(N+5)]
mod = 10**9+7

dp[N][0] = 1
# DP = np.array(dp)
# print(DP)
mul = 1
for i in reversed(range(N)):
    if(S[i]=='?'):
        c = -1
    else:
        c = int(S[i])

    for j in range(10):
        if(c != -1 and c != j):
            continue
        for k in range(13):
            dp[i][(j*mul+k)%13] += dp[i+1][k]
            dp[i][(j*mul+k)%13] %= mod
    mul *=10
    mul %=13
# DP = np.array(dp)
result = dp[0][5]
# print(DP)
print(result)

Submission status: Time Limit Exceeded

Solution code:
S=input()
modn=10**9+7
qnum=S.count('?')
lenS=len(S)

if S[0]=='?':
    dp=[1]*10+[0]*3
else:
    dp=[0]*13
    dp[int(S[0])]=1

for i in range(1,lenS):
    dppre = dp
    dp = [0] * 13
    if S[i] == '?':
        R = range(10)
    else:
        R = [int(S[i])]
    
    for j in range(13):
        for k in R:
            dp[(j * 10 + k) % 13 ] += dppre[j]
    for j in range(13):
        dp[j] %= modn

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def solve(s):
    MOD = 10 ** 9 + 7
    dp = np.zeros(13, dtype=np.int64)
    dp[0] = 1
    idx = np.zeros(13, dtype=np.int8)
    for i in range(13):
        idx[i * 10 % 13] = i
    window = np.ones(10, dtype=np.int8)
    for c in s:
        if c == '?':
            dp = np.convolve(dp[idx], window)
            dp[:9] += dp[13:]
            dp = dp[:13] % MOD
        else:
            dp = np.roll(dp[idx], int(c))
    return dp[5]


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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def solve(s):
    MOD = 10 ** 9 + 7
    dp = np.zeros(13, dtype=np.int64)
    dp[0] = 1
    idx = np.zeros(13, dtype=np.int8)
    for i in range(13):
        idx[i * 10 % 13] = i
    window = np.ones(10, dtype=np.int8)
    for c in s:
        if c == '?':
            dp = np.convolve(dp[idx], window) % MOD
            dp[:9] += dp[13:]
            dp = dp[:13] % MOD
        else:
            dp = np.roll(dp[idx], int(c))
    return dp[5]


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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def solve(s):
    MOD = 10 ** 9 + 7
    dp = np.zeros(13, dtype=np.int64)
    dp[0] = 1
    idx = np.zeros(13, dtype=np.int8)
    for i in range(13):
        idx[i * 10 % 13] = i
    window = np.ones(10, dtype=np.int8)
    for c in s:
        if c == '?':
            ndp = np.convolve(dp[idx], window, mode='full')
            dp = ndp[:13]
            dp[:9] += ndp[13:]
            dp %= MOD
        else:
            dp = np.roll(dp[idx], int(c))
    return dp[5]


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

Submission status: Time Limit Exceeded

Solution code:
S=input()
modn=10**9+7
qnum=S.count('?')
lenS=len(S)

dpa=[0]*13
dpb=[1]+[0]*12


for i in range(lenS):
    dpa=[0]*13
    if S[i]!='?':
        num=int(S[i]) 
        for j in range(13):
            dpa[((j*10)+num)%13]=dpb[j]
            dpa[((j*10)+num)%13]%=modn
    else:
        for k in range(10):
            for j in range(13):
                dpa[((j*10)+k)%13]+=dpb[j]
                dpa[((j*10)+k)%13]%=modn
    dpb=dpa
print(dpa[5])

Submission status: Time Limit Exceeded

Solution code:
def f(s):
    rd = [[10, 11, 12], [3, 6, 9], [4, 8, 12], [1, 2, 3], [4, 7, 10], [1, 5, 9]]
    k = len(s)
    md = 10 ** 9 + 7
    dp = [[0] * 13 for _ in range(k + 1)]
    dp[0][0] = 1
    dpi = dp[0]
    for i, c in enumerate(s[::-1]):
        dpi1 = dp[i + 1]
        if c == "?":
            r1, r2, r3 = rd[i % 6]
            sm = sum(dpi)
            for j in range(13):
                dpi1[j] = (sm - (dpi[j - r1] + dpi[j - r2] + dpi[j - r3])) % md
        else:
            m = int(c) * 10 ** i % 13
            for j in range(13):
                dpi1[j] = (dpi1[j] + dpi[j - m]) % md
        dpi = dpi1
    print(dp[k][5])

s = input()
f(s)

Submission status: Time Limit Exceeded

Solution code:
s = list(input())

mod = 10**9 + 7

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

    mul = (mul*10)%N
    dp = nextDP

print(dp[5])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

S = input().rstrip()

MOD = 10 ** 9 + 7
n = len(S)

dp = np.zeros((100005, 13), dtype=np.uint64)

dp[0][0] = 1

for i in range(n):
    if S[i] == '?':
        c = -1
    else:
        c = int(S[i])
    
    for j in range(10):
        if c != -1 and c != j:
            continue
        for ki in range(13):
            dp[i+1][(ki * 10 + j) %13] += dp[i][ki]
            
    for j in range(13):
        dp[i+1][j] %= MOD
        
    res = dp[n][5]
    
print(res)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7
n = len(S)

dp = np.zeros((100005, 13), dtype=np.uint64)

dp[0][0] = 1

for i in range(n):
    if S[i] == '?':
        c = -1
    else:
        c = int(S[i])
    # print(c)
    
    for j in range(10):
        if c != -1 and c != j:
            continue
        for ki in range(13):
            dp[i+1][(ki * 10 + j) %13] += dp[i][ki]
            
    for j in range(13):
        dp[i+1][j] %= MOD
        
    res = dp[n][5]
    
print(res)