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: Runtime Error

Solution code:
import math
import copy
from copy import deepcopy
import sys
import fractions
import numpy as np
from functools import reduce
import statistics
import heapq

# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

def getInputStr():
    inputStr = str(input())
    return inputStr

data = getInputStr()

a = str(data)
listStr = []
listStr = list(a)

del listStr[len(listStr)-1]
listStr.reverse()

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

INF = 10 ** 9 + 7

for i in range(len(listStr)):
    if i ==0:
        keta = 1
    else:
        keta = pow(10, i)

    if listStr[i] == "?":
        for k in range(10):
            for j in range(13):
                dp[i+1][int(((k*keta)%13 + j) % 13)] += dp[i][j]
                # dp[i + 1][int(((k * ordinal) + j) % 13)] %= INF
    else:
        k = int(listStr[i])
        for j in range(13):
            dp[i + 1][int(((k*keta)%13 + j) % 13)] += dp[i][j]
            # dp[i + 1][int(((k*ordinal) + j) % 13)] %= INF


ans = dp[len(listStr)][5] % INF
print(ans)

Submission status: Runtime Error

Solution code:
import math
import copy
from copy import deepcopy
import sys
import fractions
import numpy as np
from functools import reduce
import statistics
import heapq

input = sys.stdin.readline
sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

def getInputStr():
    inputStr = str(input())
    return inputStr

data = getInputStr()

a = str(data)
listStr = []
listStr = list(a)

del listStr[len(listStr)-1]
# listStr.reverse()

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

INF = 10 ** 9 + 7

for i in range(len(listStr)):
    if i ==0:
        keta = 1
    else:
        keta = pow(10, i)

    if listStr[i] == "?":
        for k in range(10):
            for j in range(13):
                dp[i+1][int(((k*keta)%13 + j) % 13)] += dp[i][j]
                # dp[i + 1][int(((k * ordinal) + j) % 13)] %= INF
    else:
        k = int(listStr[i])
        for j in range(13):
            dp[i + 1][int(((k*keta)%13 + j) % 13)] += dp[i][j]
            # dp[i + 1][int(((k*ordinal) + j) % 13)] %= INF


ans = dp[len(listStr)][5] % INF
print(ans)

Submission status: Runtime Error

Solution code:
import math
import copy
from copy import deepcopy
import sys
import fractions
import numpy as np
from functools import reduce
import statistics
import heapq

input = sys.stdin.readline
sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

def getInputStr():
    inputStr = str(input())
    return inputStr

data = getInputStr()

a = str(data)
listStr = []
listStr = list(a)

# del listStr[len(listStr)-1]
listStr.reverse()

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

INF = 10 ** 9 + 7

for i in range(len(listStr)):
    if i ==0:
        keta = 1
    else:
        keta = pow(10, i)

    if listStr[i] == "?":
        for k in range(10):
            for j in range(13):
                dp[i+1][int(((k*keta)%13 + j) % 13)] += dp[i][j]
                # dp[i + 1][int(((k * ordinal) + j) % 13)] %= INF
    else:
        k = int(listStr[i])
        for j in range(13):
            dp[i + 1][int(((k*keta)%13 + j) % 13)] += dp[i][j]
            # dp[i + 1][int(((k*ordinal) + j) % 13)] %= INF


ans = dp[len(listStr)][5] % INF
print(ans)

Submission status: Runtime Error

Solution code:
import math
import copy
from copy import deepcopy
import sys
import fractions
import numpy as np
from functools import reduce
import statistics
import heapq

input = sys.stdin.readline
sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

def getInputStr():
    inputStr = str(input())
    return inputStr

data = getInputStr()

a = str(data)
listStr = []
listStr = list(a)

del listStr[len(listStr)-1]
listStr.reverse()

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

INF = 10 ** 9 + 7

for i in range(len(listStr)):
    if listStr[i] == "?":
        for k in range(10):
            for j in range(13):
                dp[i+1][int(((k*ordinal) + j) % 13)] += dp[i][j]
                dp[i + 1][int(((k * ordinal) + j) % 13)] %= INF
    else:
        k = int(listStr[i])
        for j in range(13):
            tmp = int()
            dp[i + 1][int(((k*ordinal) + j) % 13)] += dp[i][j]
            dp[i + 1][int(((k*ordinal) + j) % 13)] %= INF
    ordinal = ordinal * 10 % 13

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

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
def saiki(num,lis):
    if num==6:
        temp=0
        for i in range(6):
            temp+=lis[i]*10**(5-i)
        if (temp+amari)%13==5:
            cand.append(lis)
        return 0
    else:
        for i in range(10):
            saiki(num+1,lis+[i])
            

S=list(input())
N=len(S)

num=[0]*6#左から大きい
que=[0]*6

for i in range(N):
    if S[i]=="?":
        que[i%6]+=1
    else:
        num[i%6]+=int(S[i])

for i in range(6):
    num[i]%=10
amari=0
for i in range(6):
    amari+=(num[i]*10**(5-i))%13
amari%=13

cand=[]
saiki(0,[])

#print(amari)
#print(cand)
"""
ans=0
for item in cand:
    temp=1
    for i in range(6):
        if que[i]==0 and item[i]!=0:
            temp=0
            break
        else:
            for j in range(que[i]-1):
                temp*=(item[i]+que[i]-j-1)
    ans+=temp
    """
    """
    if temp!=0:
        print(item)
        print(ans)
    """
    """
print(ans%(10**9+7))
            
"""

Submission status: Runtime Error

Solution code:
MOD = 10**9+7
# dp[i][j] := Sの後ろからi桁を13で割った余りがjとなるようなものの個数
S = input()
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 k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= MOD
    else:
        k = int(x) # これしか選ぶ余地なし
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= MOD
    mul = mul * 10 % 13
print(dp[l][5])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

# dp[dgt][mo] := dgt桁目まで確定していて, そこまでで13で割った余りがmoである組み合わせ
# ?であるときは, その数にしかできないため, その数をつかう
# ?であるときは0~9を全て試して遷移させよう
def main():
    S = input()
    l = len(S)
    dp = [[0]*(13) for _ in range(10**5)]
    dp[0][0] = 1
    for dgt in range(l):
        for mo in range(13):
            if S[dgt]=="?":
                for nxt in range(10):
                    dp[dgt+1][(mo * 10 + nxt)%13] += dp[dgt][mo]
            else:
                dp[dgt+1][(mo*10 + int(S[dgt]))%13] += dp[dgt][mo]
    print(dp[l][5]%MOD)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int main(){
  string S;
  cin >> S;
  vector<int> R(13);
  for (int i=0;i<13;i++){
    R.at(i) = (10 * i) % 13;
  }
  vector<int> ML(13);
  for (int i=0;i<13;i++){
    ML.at(i) = 0;
  }
  ML.at(0) = 1;
  for (int i=0;i<S.size();i++){
    vector<int> NL(13);
    if (S.at(i) == '?'){
      for (int j=0;j<130;j++){
        NL.at(j%13) += ML.at(((j/10)*10)%13);
        NL.at(j%13) %= mod;
      }
    }
    else{
      string t = "";
      t = S.at(i);
      int d = stoi(t);
      for (int j=0;j<13;j++){
        NL.at((10*j+d)%13) += ML.at((j*10)%13);
        NL.at((10*j+d)%13) %= mod;
      }
    }
    if (i != S.size() - 1){
      for (int m=0;m<13;m++){
        ML.at((10*m)%13) = NL.at(m);
      }
    }
    else{
      for (int m=0;m<13;m++){
        ML.at(m) = NL.at(m);
      }
    }
  }
  cout << ML.at(5) << endl;
}

Submission status: Runtime Error

Solution code:
def main():
    S = input()
    N = len(S)
    MOD = 10 ** 9 + 7
    dp = [[0] * 12 for _ in range(N + 5)]
    dp[0][0] = 1

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

    print(dp[N][5])

    

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n = int(input().strip())
a = list(map(int, input().strip().split()))

box=[0]*n
ans=[]
for i in range(n,0,-1):
    sum_=0
    for j in range(1,n+1):
        if j*i>n:
            break
        sum_+=box[j*i-1]
    if sum_%2!=a[i-1]:
        box[i-1]=1
        ans.append(i)

print(len(ans))
print(' '.join(list(map(str,ans))))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

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

#i桁目までみて，あまりがjになるものの個数
dp=[[0]*mod for _ in range(N+1)]

#1桁目
if S[-1]!="?":
    a=int(S[-1])
    for j in range(mod):
        dp[1][a]=1
else:
    for j in range(mod):
        for k in range(10):
            dp[1][k]=1

for i in range(1,N):
    if S[-i-1]!="?":
        a=(pow(10,i)*int(S[-i-1]))%mod
        for j in range(mod):
            dp[i+1][(j+a)%mod]=dp[i][j]
    else:
        a=pow(10,i)%mod
        for j in range(mod):
            for k in range(10):
                dp[i+1][(j+k*a)%mod]+=dp[i][j]
                dp[i+1][(j+k*a)%mod]%=mod2

print(dp[-1][5])

Submission status: Runtime Error

Solution code:
%%time
from copy import deepcopy
rotate = lambda x,y:x[y:] + x[:y]
S = input()
mod = 13
amari = 5

dp_tmp = [0]*13
dp_tmp[0] = 1
for i,s in enumerate(S[::-1]):
    dp = [0]*13
    if s == "?":
        for n in range(10):
            dp_tmp_roll = rotate(dp_tmp,n*(10**i)%mod)
            for i in range(13):
                dp[i] += dp_tmp_roll[i]
    else:
        dp_tmp_roll = rotate(dp_tmp,int(s)*(10**i)%mod)
        for i in range(13):
            dp[i] += dp_tmp_roll[i]
    for n in range(13):
        dp[n] = dp[n]%(10**9+7)
    dp_tmp = deepcopy(dp)
print(dp[amari])

Submission status: Runtime Error

Solution code:
S = input()
mod = 13
amari = 5

import numpy as np
dp = np.zeros((len(N)+1,mod),dtype="uint64")
dp[0,0%mod] = 1
for i,s in enumerate(S):
    if s == "?":
        for n in range(10):
            dp[i+1,:] += np.roll(dp[i],n*(10**i)%mod)
    else:
        dp[i+1,:] += np.roll(dp[i],int(s)*(10**i)%mod)
    dp = dp%(10**9+7)
print(dp[-1,amari+1])

Submission status: Runtime Error

Solution code:
def main():
    from sys import stdin
    input=stdin.readline
    s = list(reversed(input()))
    mod = 10**9+7
    memo = [0 for _ in [0]*13]
    m13 = [(10**i) % 13 for i in range(12)]
    memo[0] = 1
    for i in range(len(s)):
        memo2 = [0 for _ in [0]*13]
        a = m13[i % 12]
        if s[i] == "?":
            list_ = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        else:
            list_ = [int(s[i])]
        list_ = [(a*j) % 13 for j in list_]
        for l in list_:
            for j in range(13):
                memo2[(l+j) % 13] += memo[j]
        memo = [j % mod for j in memo2]
    print(memo[5])


main()

Submission status: Runtime Error

Solution code:
def main():
    import numpy as np
    s = list(reversed(input()))
    mod = 10**9+7
    memo = np.zeros(13, dtype=np.int64)
    m13 = [(10**i) % 13 for i in range(12)]
    npa13 = np.array([i * np.arange(10) % 13 for i in range(12)])
    memo[0] = 1
    for j, i in enumerate(s):
        memo2 = np.zeros(13, dtype=np.int64)
        a = m13[j % 12]
        if i == "?":
            for l in npa13[a]:
                memo2[l:] += memo[:13-l]
                memo2[:l] += memo[13-l:]
            memo = memo2 % mod
        else:
            l = a*int(i) % 13
            memo = np.append(memo[:13-l],memo[13-l:]) % mod
    print(int(memo[5]))


main()

Submission status: Runtime Error

Solution code:
interesting

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

def main():
  s = input()
  n = len(s)
  mod = 10**9+7
  dp = [[0]*13 for _ in range(n+1)]
  dp[0][0] = 1
  d = {(j, k):(10*j+k)%13 for k in range(10) for j in range(13)}
  for i in range(n):
    if s[i] != "?":
      t = int(s[i])
      for j in range(13):
        dp[i+1][d[(j, t)]] += dp[i][j]
        dp[i+1][d[(j, t)]] %= mod
    else:
      for k in range(10):
        for j in range(13):
          dp[i+1][d[(j, k)]] += dp[i][j]
          dp[i+1][d[(j, k)]] %= mod
  print(dp[n][5]%mod)
if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

def main():
  s = input()
  n = len(s)
  mod = 10**9+7
  dp = [[0]*13 for _ in range(n+1)]
  dp[0][0] = 1
  d = {(j, k):(10*j+k)%13 for k in range(10) for j in range(13)}
  for i in range(n):
    if s[i] != "?":
      t = int(s[i])
      for j in range(13):
        dp[i+1][d[(j, t)]] += dp[i][j]
        dp[i+1][d[(j, t)]] %= mod
    else:
      for k in range(10):
        for j in range(13):
          dp[i+1][d[(j, k)]] += dp[i][j]
          dp[i+1][d[(j, k)]] %= mod
  print(dp[n][5]%mod)

if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

def main():
  s = input()
  n = len(s)
  mod = 10**9+7
  dp = [[0]*13 for _ in range(n+1)]
  dp[0][0] = 1
  d = {(j, k):(10*j+k)%13 for k in range(10) for j in range(13)}
  for i in range(n):
    if s[i] != "?":
      t = int(s[i])
      for j in range(13):
        dp[i+1][d[(j, t)]] += dp[i][j]
        dp[i+1][d[(j, t)]] %= mod
    else:
      for k in range(10):
        for j in range(13):
          dp[i+1][d[(j, k)]] += dp[i][j]
          dp[i+1][d[(j, k)]] %= mod
  print(dp[n][5]%mod)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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

if s[0]!='?':
    a=int(s[i])*10**(n-1)%13
    dp[0][a]=1
else:
    for k in range(10):
        a=k*10**(n-1)%13
        dp[0][a]=1

for i in range(1,n):
    if s[i]!='?':
        a=int(s[i])*10**(n-i-1)%13
        for j in range(13):
            dp[i][j]+=dp[i-1][(j-a)%13]
    else:
        for k in range(10):
            a=k*10**(n-i-1)%13
            for j in range(13):
                dp[i][j]+=dp[i-1][(j-a)%13]
print(dp[n-1][5]%(10**9+7))

Submission status: Runtime Error

Solution code:
S = input()
n = len(S)
mod = 10**9 + 7
pow10 = [0]
for i in range(1,n):
    x = pow10[-1]
    y = 10*x%13
    pow10.append(y)
dp = [[0 for i in range(13)]for j in range(n+1)]
dp[0][0] = 1
for i in range(n):
    d = S[-i-1]
    if d = '?':
        for j in range(10):
            s = pow10[i]*j%13
            for t in range(13):
                r = (s+t)%13
                dp[i][r] = (dp[i][r] + dp[i-1][t])%mod
    else:
        j = str(d)
        s = pow10[i]*j%13
        for t in range(13):
            r = (s+t)%13
            dp[i][r] = (dp[i][r] + dp[i-1][t])%mod
print(dp[n][5])

Submission status: Runtime Error

Solution code:
import numpy as np

S = input()
mod = int(10**9 + 7)
dp = np.zeros(13)
dp[0] = 1

M = np.zeros((13, 13))
for i in range(13):
    for d in range(10):
        M[i][(i * 10 + d) % 13] += 1

for i in range(len(S)):
    ndp = np.zeros(13)
    if S[i] == '?':
        ndp = np.matmul(dp, M)
    else:
        d = int(S[i])
        for j in range(13):
            ndp[(j * 10 + d) % 13] += dp[j]
    dp = np.mod(ndp, 1000000007)

print(int(dp[5]))

Submission status: Runtime Error

Solution code:
    import numpy as np
     
    s = input()
    p = np.array([0]*13)
    p[0] = 1
     
    amari = [[0]*13 for _ in range(13)]
    for j in range(10):
      for i in range(13):
        amari[i][(i*10+j)%13] += 1
    M = np.array(amari)
     
    for si in range(len(s)):
      a = np.array([0]*13)
      if s[si] == '?':
        a = np.dot(p,M)
      else:
        c = int(s[si])
        for i in range(13):
          a[(i*10+c)%13] += p[i]
      p = np.mod(a,1000000007)
    print(p[5])

Submission status: Runtime Error

Solution code:
import numpy as np

S = input()
mod = int(10**9 + 7)
dp = np.zeros(13)
dp[0] = 1

M = np.zeros((13, 13))
for i in range(13):
    for d in range(10):
        M[i][(i * 10 + d) % 13] += 1

for i in range(len(S)):
    ndp = np.zeros(13)
    if S[i] == '?':
        ndp = np.matmul(dp, M)
    else:
        d = int(S[i])
        for j in range(13):
            ndp[(j * 10 + d) % 13] += dp[j]
    dp = np.mod(ndp, mod)

print(int(dp[5]))

Submission status: Runtime Error

Solution code:
import numpy as np

S = input()
mod = 10**9 + 7
dp = np.zeros(13)
dp[0] = 1

M = np.zeros((13, 13))
for i in range(13):
    for d in range(10):
        M[i][(i * 10 + d) % 13] += 1

for i in range(len(S)):
    ndp = np.zeros(13)
    if S[i] == '?':
        ndp = np.matmul(dp, M)
    else:
        d = int(S[i])
        for j in range(13):
            ndp[(j * 10 + d) % 13] += dp[j]
    dp = np.mod(ndp, mod)

print(int(dp[5]))

Submission status: Runtime Error

Solution code:
import numpy as np

S = input()
mod = 10**9 + 7
dp = np.zeros(13)
dp[0] = 1

M = np.zeros((13, 13))
for i in range(13):
    for d in range(10):
        M[i][(i * 10 + d) % 13] += 1

for i in range(len(S)):
    ndp = np.zeros(13)
    if S[i] == '?':
        ndp = np.matmul(dp, M)
    else:
        d = int(S[i])
        for j in range(13):
            ndp[(j * 10 + d) % 13] += dp[j]
    dp = ndp % mod

print(int(dp[5]))

Submission status: Runtime Error

Solution code:
import numpy as np

S = input()
mod = 10**9 + 7
dp = np.zeros(13)
dp[0] = 1

M = np.zeros((13, 13))
for i in range(13):
    for d in range(10):
        M[i][(i * 10 + d) % 13] += 1

for i in range(len(S)):
    ndp = np.zeros(13)
    if S[i] == '?':
        ndp = np.matmul(dp, M)
    else:
        d = int(S[i])
        for j in range(13):
            ndp[(j * 10 + d) % 13] += dp[j]
    dp = ndp % mod
print(int(dp[5])

Submission status: Runtime Error

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

s = sys.stdin.readline()
n = len(s)
now = [0] * 13
now[0] = 1
for i in range(n,-1,-1):
    prev = now[::]
    now = [0] * 13
    c = n - i - 1#桁
    if s[i] == '?':
        for k in range(10):
            l = (k*10**c) % 13
            for j in range(13):
                now[(j+l)%13] += prev[j]
                now[(j+l)%13] = now[(j+l)%13] % mod
    else:
        l = (int(s[i])*10**c) % 13
        for j in range(13):
            now[(j+l)%13] = prev[j]    
            now[(j+l)%13] = now[(j+l)%13] % mod
    # print(now)
print(now[5])

Submission status: Runtime Error

Solution code:
n=input()
l1=list(n)
l1=l1[::-1]
num=len(n)
ans=[0 for i in range(13)]
if l1[0]=="?":
  for i in range(0,10):
    ans[i]=1
else:
  ans[int(l1[0])]=1
for i in range(1,num):
  mod=(10**i)%13
  dp=[ans[i] for i in range(13)]
  if l1[i]=="?":
    lmod=[(j*mod)%13 for j in range(10)]
    for j in range(13):
      ans1=0
      for k in lmod:
        if j-k>=0:
          mod2=j-k
        else:
          mod2=13+j-k
        ans1=(ans1+dp[mod2])%(10**9+7)
      ans[j]=ans1%(10**9+7)
  else:
    num1=int(l1[i])
    mod1=(num1*mod)%13
    for j in range(13):
      if j-mod1>=0:
        mod2=j-mod1
      else:
        mod2=13+j-mod1
      ans[j]=dp[mod2]
print(l[num-1][5]%(10**9+7))

Submission status: Runtime Error

Solution code:
S = input()
 
MOD = 10 ** 9 + 7
N = 13
 
DP = [0] * N
 
# 初期値
DP[0] = 1
digit = 1
 
# 0 -> 5 -> ?5 -> ??5 -> ...に対する余りがどこになるかを更新していく
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 * digit + j) % N] += DP[j]
                nextDP[(k * digit + j) % N] %= MOD
    else:
        k = int(S[i])
        for j in range(N):
            nextDP[(k * digit + j) % N] += DP[j]
            nextDP[(k * digit + j) % N] %= MOD
 
    digit *= 10
    digit %= N
    DP = nextDP[:]
 
print(DP[5])
 
 
 
S = input()

MOD = 10 ** 9 + 7
N = 13

DP = [0] * N

# 初期値
DP[0] = 1
digit = 1

# 0 -> 5 -> ?5 -> ??5 -> ...に対する余りがどこになるかを更新していく
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 * digit + j) % N] += DP[j]
                nextDP[(k * digit + j) % N] %= MOD
    else:
        k = int(S[i])
        for j in range(N):
            nextDP[(k * digit + j) % N] += DP[j]
            nextDP[(k * digit + j) % N] %= MOD

    digit *= 10
    digit %= N
    DP = nextDP[:]

print(DP[5])

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

def dp(i,j):
    if(i==1):
        if(S[i]=="?"):
            if(j<=9):
                return 1
            else:
                return 0
        else:
            if(int(S[i])==j):
                return 1
            else:
                return 0
            
    else:
        if(S[i] != "?"):
            #print(error)
            a = int(S[i])
            r = a*(10**(i-1))
            #print(r)
            count = 0
            for k in range(0,13):
                if((r+k)%13 == j):
                    count += dp(i-1,k)

            return count
        else:

            sum_ = 0
            for k in range(0,13):#
                count = 0
                dp_ = dp(i-1,k)
                if(dp_>0):
                    for l in range(0,10):
                        x = l*(10**(i-1))
                        
                        if((x+k)%13==j):
                            count += 1
                            #print(x+k)
                        
                sum_ += count*dp_
                #if(count>0 and dp_>0):
                  #  print(count,dp_,x)
            
            return sum_
    
print(int(dp(len(S)-1,5)%(1e+9+7)))

Submission status: Runtime Error

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)
S = str(input())
N = len(S)
M = 13
c = [0]*(N)
for i in range(N):
    c[i] = (10**i)%M
#    c[i] = pow(10,i,M)
#print(c)
c.reverse()
#print(c)
"""
dp = [[0]*M for _ in range(N+1)]
i = int(0)
for j in range(M):
    dp[0][j] = 1
for s in S:
    if s == "?":
        for l in range(10):
            m = l * c[i] % M
            dp[i+1][(M - m) % M] += dp[i][j]
    else:
        m = int(s) * c[i] % M
        dp[i][(M - m) % M] +=dp[i][j]
    i +=1




dp = [[0]*M for _ in range(N)]
c = (10**(N-1))%M
if S[0] == "?":
    for l in range(10):
        dp[0][l*c%M] += 1
else:
    m = int(S[0]) * c%M
    dp[0][m] = 1
S = S[1:]
i = int(1)
for s in S:
    c = (10 ** (N - 1-i)) % M
    if s == "?":
        for j in range(13):
            for l in range(10):
                dp[i][j] += dp[i-1][(j-l*c)%13]
    else:
        st = int(s)
        for j in range(13):
            dp[i][j] = dp[i-1][(j-st*c)%13]
    i +=1

"""
dp = [[0]*M for _ in range(N)]
if S[0] == "?":
    for l in range(10):
        m = l * c[0]%M
        dp[0][m] += 1
else:
    m = int(S[0]) * c[0]%M
    dp[0][m] = 1

for i in range(1,N):
    if S[i] == "?":
        for j in range(M):
            for l in range(10):
                m = l*c[i]%M
                dp[i][j] += dp[i-1][(M+j-m)%M]%mod
    else:
        for j in range(M):
            m = int(S[i])*c[i]%M
            dp[i][j] = dp[i-1][(M+j-m)%M]%=mod

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

Submission status: Runtime Error

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)
S = str(input())
N = len(S)
M = 13
c = [0]*(N)
for i in range(N):
    c[i] = (10**i)%M
#    c[i] = pow(10,i,M)
#print(c)
c.reverse()
#print(c)
"""
dp = [[0]*M for _ in range(N+1)]
i = int(0)
for j in range(M):
    dp[0][j] = 1
for s in S:
    if s == "?":
        for l in range(10):
            m = l * c[i] % M
            dp[i+1][(M - m) % M] += dp[i][j]
    else:
        m = int(s) * c[i] % M
        dp[i][(M - m) % M] +=dp[i][j]
    i +=1




dp = [[0]*M for _ in range(N)]
c = (10**(N-1))%M
if S[0] == "?":
    for l in range(10):
        dp[0][l*c%M] += 1
else:
    m = int(S[0]) * c%M
    dp[0][m] = 1
S = S[1:]
i = int(1)
for s in S:
    c = (10 ** (N - 1-i)) % M
    if s == "?":
        for j in range(13):
            for l in range(10):
                dp[i][j] += dp[i-1][(j-l*c)%13]
    else:
        st = int(s)
        for j in range(13):
            dp[i][j] = dp[i-1][(j-st*c)%13]
    i +=1

"""
dp = [[0]*M for _ in range(N)]
if S[0] == "?":
    for l in range(10):
        m = l * c[0]%M
        dp[0][m] += 1
else:
    m = int(S[0]) * c[0]%M
    dp[0][m] = 1

for i in range(1,N):
    if S[i] == "?":
        for j in range(M):
            for l in range(10):
                m = l*c[i]%M
                dp[i][j] += dp[i-1][(M+j-m)%M]%mod
    else:
        for j in range(M):
            m = int(S[i])*c[i]%M
            dp[i][j] = dp[i-1][(M+j-m)%M]
    for j in range(M):
        dp[i][j] %=mod

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

Submission status: Runtime Error

Solution code:
import sys
 
input = sys.stdin.readline
mod = 10 ** 9 + 7
s = str(input().rstrip('\n'))
ls = [[0] * 13 for _ in range(len(s))]
for i in range(len(s)):
    if i == 0:
        if s[-i-1] == "?":
            for j in range(10):
                ls[i][j] += 1
        else:
            ls[i][int(s[-i-1])] += 1
    else:
        mult = pow(10, i, 13)
        if s[-i-1] == "?":
            for j in range(13):
                for k in range(10):
                    ls[i][(k * mult + j) % 13] += ls[i-1][j]
        else:
            st = int(s[-i-1])
            for j in range(13)　　　
        　　　　ls[i][(st * mult + j) % 13] += ls[i-1][j]
    for j in range(13):
        ls[i][j] = ls[i][j] % mod
print(ls[-1][5])