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

Solution (Python):
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

s = ns()
n = len(s)

class ModInt:
    def __init__(self, n=0, mod=mod):
        self.mod = mod
        self.n = n % self.mod
    
    def value(self):
        return self.n
    
    def __add__(self, rhs):
        if isinstance(rhs, ModInt):
            return self.__class__(self.n + rhs.n, self.mod)
        return self.__class__(self.n + rhs, self.mod)
    
    __radd__ = __add__
    
    def __sub__(self, rhs):
        if isinstance(rhs, ModInt):
            return self.__class__(self.n - rhs.n, self.mod)
        return self.__class__(self.n - rhs, self.mod)
    
    def __rsub__(self, lhs):
        if isinstance(lhs, ModInt):
            return self.__class__(lhs.n - self.n, self.mod)
        return self.__class__(lhs - self.n, self.mod)

    def __mul__(self, rhs):
        if isinstance(rhs, ModInt):
            return self.__class__(self.n * rhs.n, self.mod)
        return self.__class__(self.n * rhs, self.mod)
    
    __rmul__ = __mul__

    def __floordiv__(self, rhs):
        if isinstance(rhs, ModInt):
            return self.__class__(self.n // rhs.n, self.mod)
        return self.__class__(self.n // rhs, self.mod)
    
    def __rfloordiv__(self, lhs):
        if isinstance(lhs, ModInt):
            return self.__class__(lhs.n // self.n, self.mod)
        return self.__class__(lhs // self.n, self.mod)

    def __iadd__(self, rhs):
        if isinstance(rhs, ModInt):
            self.n += rhs.n
        else:
            self.n += rhs
        if self.n >= self.mod:
            self.n -= self.mod
        
        return self
    
    def __isub__(self, rhs):
        rhs_n = rhs.n if isinstance(rhs, ModInt) else rhs
        if self.n < rhs_n:
            self.n += self.mod
        self.n -= rhs_n
        return self
    
    def __imul__(self, rhs):
        rhs_n = rhs.n if isinstance(rhs, ModInt) else rhs
        self.n = self.n * rhs_n % self.mod
        return self
    
    def __ifloordiv__(self, rhs):
        rhs_n = rhs.n if isinstance(rhs, ModInt) else rhs
        exp = self.mod - 2
        while exp:
            if exp % 2:
                self *= rhs_n
            
            rhs_n *= rhs_n
            rhs_n %= self.mod
            exp //= 2
        
        return self
    
    def __pow__(self, exp):
        exp_n = exp.n if isinstance(exp, ModInt) else exp
        if exp_n == 0:
            return self.__class__(1, self.mod)
        if exp_n % 2 == 0:
            t = self.__pow__(exp_n // 2)
            return t * t
        return self * self.__pow__(exp_n - 1)
    
    def __str__(self):
        return str(self.n)

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

dp2 = [0] * (n + 7)
dp2[0] = 1
for i in range(n + 6):
    dp2[i + 1] = dp2[i] * 10 % 13

for i in range(n):
    for j in range(13):
        if s[i] != '?':
            dig = int(s[i])
            t = dp2[n - i - 1] * dig + j
            t %= 13
            ni = i + 1
            nj = t
            dp[ni][nj] += dp[i][j]
            dp[ni][nj] %= mod
        else:
            for k in range(10):
                dig = k
                t = dp2[n - i - 1] * dig + j
                t %= 13
                ni = i + 1
                nj = t
                dp[ni][nj] += dp[i][j]
                dp[ni][nj] %= mod

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

Solution (Python):
from itertools import accumulate

def solve():
    MOD = 10**9 + 7

    Ss = input()

    dp = [0] * 13
    dp[0] = 1
    for d, Sd in enumerate(Ss):
        dp2 = [0] * 26
        for mod13 in range(13):
            if Sd != '?':
                x = int(Sd)
                mod13n = (10*mod13 + x) % 13
                dp2[mod13n] += dp[mod13]
                dp2[mod13n+1] -= dp[mod13]
            else:
                mod13n = (10*mod13 + 0) % 13
                dp2[mod13n] += dp[mod13]
                dp2[mod13n+10] -= dp[mod13]
        dp2 = list(accumulate(dp2))
        dp = [(a+b) % MOD for a, b in zip(dp2[:13], dp2[13:])]

    print(dp[5])


solve()

Solution (Python):
import sys


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    S = input()
    N = len(S)
    dp = [[0] * 13 for _ in range(N)]

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

    tenfactor = 1
    for i in range(1, N):
        tenfactor *= 10
        tenfactor %= 13

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

    print(dp[-1][5])


if __name__ == "__main__":
    main()

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

if S[0] == "?":
    for i in range(10):
        dp[i][0] = 1
else:
    dp[int(S[0])][0] = 1
        
for i in range(1, N):
    if S[i] == "?":
        for s in range(10):
            for x in range(13):
                dp[(x*10 + s)%13][i] += dp[x][i-1]
    else:
        for x in range(13):
            dp[(x*10 + int(S[i]))%13][i] += dp[x][i-1] 
    for t in range(13):
        dp[t][i] = dp[t][i]%mod
print(dp[5][N-1])

Solution (Python):
MOD = 10 ** 9 + 7
pow_10_i_13 = [pow(10, i, 13) for i in range(6)]

s = input()

dp = [0] * 13
dp[0] = 1
for i, c in enumerate(reversed(s)):
    if c == '?':
        tmp = [0] * 13
        for j in range(10):
            shift = j * pow_10_i_13[i % 6] % 13
            for k in range(13):
                tmp[k] += dp[k-shift]
                tmp[k] %= MOD
        dp = tmp
    else:
        shift = int(c) * pow_10_i_13[i % 6] % 13
        dp = dp[-shift:] + dp[:-shift]

print(dp[5])

Solution (Python):
MOD = 10**9 + 7

Ss = input().rstrip()

lenS = len(Ss)

dp = [[0]*(13) for _ in range(lenS+1)]
dp[0][0] = 1
for i, S in enumerate(Ss):
    for j in range(13):
        dp[i][j] %= MOD
    if S != '?':
        S = int(S)
        for j in range(13):
            j2 = (j*10+S) % 13
            dp[i+1][j2] += dp[i][j]
    else:
        for S in range(10):
            for j in range(13):
                j2 = (j*10+S) % 13
                dp[i+1][j2] += dp[i][j]

ans = dp[lenS][5] % MOD
print(ans)

Solution (Python):
def main():
    MOD = 10**9 + 7
    S = input()
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(N + 1)]
    dp[0][0] = 1
    for i, c in enumerate(S):
        for j in range(10):
            if c != '?' and c != str(j):
                continue
            for k in range(13):
                dp[i + 1][(10 * k + j) % 13] += dp[i][k]
        for k in range(13):
            dp[i + 1][k] %= MOD
    print(dp[N][5])


if __name__ == '__main__':
    main()

Solution (Python):
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)


def main():
    S = input()
    MOD = 10 ** 9 + 7
    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[len(S)][5])


if __name__ == "__main__":
    main()

Solution (Python):
K = 1000000007
S = input()
l = len(S)
li = [1] + [0] * 12
work_lists = [[0] * 13 for i in range(6)]
for i in range(6):
    for x in range(10):
        work_lists[i][(x * (10 ** i)) % 13] = 1
for i in range(l):
    s = S[l - i - 1]
    if s == "?":
        work_li = work_lists[i % 6]
        next_li = [sum([work_li[j] * li[(k - j) % 13] for j in range(13)]) % K for k in range(13)]
    else:
        n = int(s)
        r = (n * (10 ** (i % 6))) % 13
        next_li = [li[(j - r) % 13] for j in range(13)]
    li = next_li
print(li[5])

Solution (Python):
s = str(input())
dp = [[0] * 13 for i in range(len(s)+1)]
dp[0][0] = 1
Naoppy = 1
mod = 13
ansmod = 10 ** 9 + 7
ans = 0
for i in range(len(s)):
    if s[i] == "?":
        for j in range(10):
            for k in range(13):
                dp[i+1][(k * 10 +j)%mod] += dp[i][k]
    else:
        for k in range(13):
            dp[i+1][(k * 10 + (int(s[i])))%mod] += dp[i][k]
    for j in range(13):
        dp[i+1][j] %= ansmod
  
print(dp[len(s)][5])

Solution (Python):
S = list(input())
l = len(S)
mod = 10**9+7

A = []
a = 1
for i in range(l):
    A.append(a)
    a = (10*a) % 13

A.reverse()

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

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

Solution (Python):
MOD = 10**9+7
S = input()
l = len(S)
dp = [[0] * 13 for _ in range(l+1)]
dp[0][0] = 1
p = 1
for i in range(l):
  if(S[i] != '?'):
    n = int(S[i])
    for j in range(13):
      dp[i+1][(j*10+n)%13] += dp[i][j]
  else:
    for k in range(10):
      for j in range(13):
        dp[i+1][(j*10+k)%13] += dp[i][j]
  for j in range(13):
    dp[i+1][j] = dp[i+1][j]%MOD
  p = (p*10)%MOD    
print(dp[l][5])

Solution (Python):
MOD = 10**9 + 7
S= input()
N = len(S)

def dpinit(ps, val=0):
    res = [val for i in [0]*ps[-1]]
    for i in ps[:-1][::-1]:
        res = [res[:] for k in [0]*i]
    return res
dp = dpinit((N+1,13))

res = [(i*10) % 13 for i in range(13)]

dp[0][0] = 1
for i in range(1,N+1):
    s = S[i-1]
    if s != '?':
        s = int(s)
        for k in range(13):
            new = (res[k] + s) % 13
            dp[i][new] += dp[i-1][k]
    else:
        for s in range(10):
            for k in range(13):
                new = (res[k] + s) % 13
                dp[i][new] += dp[i-1][k]
    for k in range(13):
        dp[i][k] %= MOD
print(dp[N][5])

Solution (Python):
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):
    if s[i] == '?':
        c = -1
    else:
        c = int(s[i])
    for d in range(10):
        if c != -1 and c != d:
            continue
        for j in range(13):
            dp[i+1][(10*j+d)%13] += dp[i][j]
    
    for j in range(13):
        dp[i+1][j] %= MOD
    
print(dp[n][5])

Solution (Python):
s=input()
n=len(s)
ten=[1]
p=1
mod=10**9+7
for i in range(n-1):
    p*=10
    p%=13
    ten.append(p)
ten=ten[::-1]
dp=[0]*13
dp[0]=1
for t,c in zip(ten,s):
    newdp=[0]*13
    if c!='?':
        c=t*int(c)%13
        for i in range(13):
            newdp[(i+c)%13]=dp[i]
    else:
        for c in range(10):
            c*=t
            for i in range(13):
                newdp[(i+c)%13]+=dp[i]
                newdp[(i+c)%13]%=mod
    dp=newdp

print(newdp[5])

Solution (Python):
M=10**9+7
s=input()
r=range
k=[1]+[0]*12
for c in s:
  l=[0]*13
  for i in r(13):
    if c=='?':
      for j in r(10): l[(i*10+j)%13]+=k[i]
    else: l[(i*10+int(c))%13]+=k[i]
  for i in r(13): k[i]=l[i]%M
print(k[5])

Solution (Python):
M=10**9+7
s=input()
r=range
dp=[[0]*13,[0]*13]
dp[0][0]=1
t=0
for c in s:
  for i in r(13):
    if c=='?':
      for j in r(10):
        dp[t^1][(i*10+j)%13]+=dp[t][i]
    else:
      dp[t^1][(i*10+int(c))%13]+=dp[t][i]
  dp[t]=[0]*13
  t^=1
  for i in r(13): dp[t][i]%=M
print(dp[len(s)%2][5])

Solution (Python):
s=list(input())
n=len(s)
s.reverse()
mod=10**9+7
dp=[[0]*13 for i in range(n+1)]
dp[0][0]=1
x=1
for i in range(n):
  for j in range(13):
    if s[i]=='?':
      for k in range(10):
        dp[i+1][j]+=dp[i][(j-k*x)%13]
    else:
      dp[i+1][j]+=dp[i][(j-int(s[i])*x)%13]
    dp[i+1][j]%=mod
  x*=10
  x%=13
print(dp[n][5])

Solution (Python):
s=list(input())
n=len(s)
s.reverse()
mod=10**9+7
dp=[[0]*13 for i in range(n+1)]
dp[0][0]=1
x=1
for i in range(n):
  for j in range(13):
    if s[i]=='?':
      for k in range(10):
        dp[i+1][j]+=dp[i][(j-(k*x)%13+13)%13]
    else:
      dp[i+1][j]+=dp[i][(j-(int(s[i])*x)%13+13)%13]
    dp[i+1][j]%=mod
  x*=10
  x%=13
print(dp[n][5])

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

for i in range(len(S)):
  s = S[-(i+1)]
  if s == "?":
    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(s)
    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[len(S)][5])

Solution (Python):
s=list(input())
s.reverse()
MOD=10**9+7
dp = [[0 for _ in range(13)] for _ in range(len(s)+1)]
dp[0][0]=1
for i in range(len(s)):
    nd=s[i]
    p=pow(10,i,13)
    for mod in range(13):
        dp[i][mod] %=MOD
        for d in range(10):
            if nd != "?" and str(d)!=nd:
                continue
            nmod=(d*p + mod) % 13
            dp[i+1][nmod] += dp[i][mod]

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

Solution (Python):
s=list(input())
s.reverse()

MOD=10**9+7
dp = [[0 for _ in range(13)] for _ in range(len(s)+1)]
dp[0][0]=1
keta=1
for i in range(len(s)):
    nd=s[i]
    for mod in range(13):
        dp[i][mod] %=MOD
        if dp[i][mod]==0:
            continue

        for d in range(10):
            if nd != "?" and str(d)!=nd:
                continue
            nmod=(d*keta + mod) % 13
            dp[i+1][nmod] += dp[i][mod]
    keta*=10
    keta%=13

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

Solution (Python):
s = input()

n = len(s)
mod = 10**9+7

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

for i in range(n):
    if s[-1-i]=='?':
        p = [x*pow(10,i,13) for x in range(0,10)]
    else:
        p = [int(s[-1-i])*pow(10,i,13)]
    for j in range(13):
        for x in p:
            dp[i+1][(j+x)%13] += dp[i][j]
    for j in range(13):
        dp[i+1][j]%=mod

print(dp[-1][5])

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

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

Solution (Python):
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):
    if s[i] != "?":
        for j in range(13):
            dp[i+1][(10*j+int(s[i])) % 13] = dp[i+1][(10*j+int(s[i])) % 13] + dp[i][j] % MOD
    else:
        for k in range(10):
            for j in range(13):
                dp[i+1][(10*j+k) % 13] = dp[i+1][(10*j+k) % 13] + dp[i][j] % MOD
print(dp[n][5]%MOD)

Solution (Python):



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


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


"""
数字がabcで並んでいて、それを13で割った時の余りがpのときに、末尾にdが追加されると、
abcd = abc * 10 + d だから、これを13で割った余りは、 p*10 % 13 + d % 13 = (10 * p + d) % 13

"""

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


print(dp[-1][5])

Solution (Python):
s=input()
n=len(s)
dp=[[0]*13 for i in range(n+1)]
dp[0][0]=1
mod=10**9+7

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

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

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

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

Solution (Python):
amari = [i for i in range(10)]
p = 10**9 + 7
s =  str(input())
n = len(s)
ans = [0]*13
ans[0] = 1
for i in reversed(s):
  dp = [0]*13
  if i == '?':
    for j in range(13):
      for k in amari:
        dp[(j + k)%13] += ans[j]
  else:
    for j in range(13):
      dp[(j + amari[int(i)])%13] += ans[j]
      
  for i in range(len(dp)):
    dp[i] %= p
  ans = dp
  for i in range(len(amari)):
    amari[i] = amari[i]*10%13
print(ans[5])

Solution (Python):
S = input()
n = len(S)

MOD = 10 ** 9 + 7


dp = [[0] * 13 for _ in range(n + 1)]
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 k in range(13):
      dp[i + 1][(k * 10 + j) % 13] += dp[i][k]
  for k in range(13):
    dp[i + 1][k] %= MOD
print(dp[n][5])

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

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections
MOD = 10**9 + 7
S = sys.stdin.readline().rstrip()
dp = [[0] * 13 for _ in range(len(S)+1)]
dp[0][0] = 1

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

print (dp[-1][5])

Solution (Python):
s=input()
l=len(s)
mod = 10**9+7
dp=[[0]*13 for _ in range(l+1)]

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

Solution (Python):
def main():
  s=input()
  l=len(s)
  mod = 10**9+7
  dp=[[0]*13 for _ in range(l+1)]
  dp[0][0]=1 
  for i in range(l):
    if s[i]!="?":
      for k in range(13):
        dp[i+1][(k*10+int(s[i]))%13]+=dp[i][k]%mod
    else:
      for j in range(10):
        for k in range(13):
          dp[i+1][(k*10+j)%13]+=dp[i][k]%mod

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

if __name__ == "__main__":
    main()

Solution (Python):

import sys
S=sys.stdin.readline().strip()
N=len(S)
mod=10**9+7
S=S[::-1]

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

for i,x in enumerate(S):  
    if i==0:
        num=pow(10,i,13)
        if x!="?":
            x=int(x)
            dp[i][(x*num)%13]=1
        else:
            for x in range(10):
                dp[i][(x*num)%13]=1
    else:
        num=pow(10,i,13)
        if x!="?":
            x=int(x)
            for j in range(13):
                n=(x*num+j)%13
                dp[i][n]+=dp[i-1][j]
                dp[i][n]%=mod
        else:
            for j in range(13):
                for x in range(10):
                    n=(x*num+j)%13
                    dp[i][n]+=dp[i-1][j]
                    dp[i][n]%=mod
print dp[N-1][5]%mod

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

dp=[]
for i in range(len(S)+1):
  dp.append([0]*13)
dp[0][0]=1


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

print(dp[-1][5])

Solution (Python):
mod = 10 ** 9 + 7
inf = float("inf")

s = list(input())
n = len(s)

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

for i in range(n):
    c = inf
    if s[i] == "?":
        c = -1
    else:
        c = ord(s[i]) - ord('0')
    for j in range(10):
        if c != -1 and c != j:
            continue
        for k in range(13):
            dp[i + 1][(k * 10 + j) % 13] += dp[i][k]
    for j in range(13):
        dp[i + 1][j] %= mod
        
print(dp[n][5])

Solution (Python):
'''
たのん
DPをDP[i][j](i:前からi文字までをみている、
j:前からi文字みたとき、13で割ったあまりがjとなる数の個数)と定め、
初期値としてDP[0][0]=1とすると、
i番目の文字s[i]が整数のときはDP[i+1][(j*10+s[i])%13]+=DP[i][j]、
i番目の文字s[i]が?のときは各k(=0 to 9)について
DP[i+1][(j*10+k)%13]+=DP[i][j]と更新することで、
DP[-1][5]が求める答えに一致します。
前からi-1文字をみたときの13で割ったあまりがjであるとき、
それに1文字を付け足した数iを13で割ったあまりは、
前からi-1文字をみたときの数をnとすると、
n*10+i≡j*10+i(mod 13)より(j*10+i)%13で求められることから
上記の更新方法が出てきます。
'''
s=input()
l=len(s)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1 
for i in range(l):
 if s[i]=='?': 
   for j in range(10):
     for k in range(13):
       dp[i+1][(k*10+j)%13]+=dp[i][k]%mod
 else:
   for k in range(13): 
     dp[i+1][(k*10+int(s[i]))%13]+=dp[i][k]%mod
print(dp[-1][5]%mod)

Solution (Python):
'''
たのん
DPをDP[i][j](i:前からi文字までをみている、j:前からi文字みたとき、
13で割ったあまりがjとなる数の個数)と定め、
初期値としてDP[0][0]=1とすると、
i番目の文字s[i]が整数のときはDP[i+1][(j*10+s[i])%13]+=DP[i][j]、
i番目の文字s[i]が?のときは各k(=0 to 9)について
DP[i+1][(j*10+k)%13]+=DP[i][j]と更新することで、
DP[-1][5]が求める答えに一致します。
このDPの計算量はO(N)(定数倍は最悪の場合10*13=130倍程度)になります。
前からi-1文字をみたときの13で割ったあまりがjであるとき、
それに1文字を付け足した数iを13で割ったあまりは、
前からi-1文字をみたときの数をnとすると、
n*10+i≡j*10+i(mod 13)より(j*10+i)%13で求められることから
上記の更新方法が出てきます。
'''
s=input()
l=len(s)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1 
for i in range(l):
 if s[i]=='?': 
   for j in range(10):
     for k in range(13):
       dp[i+1][(k*10+j)%13]+=dp[i][k]%mod
 else:
   for k in range(13): 
     dp[i+1][(k*10+int(s[i]))%13]+=dp[i][k]%mod
print(dp[-1][5]%mod)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

s = readline().rstrip().decode()
mod = 10 ** 9 + 7
ans = [0] * 13
ans[0] = 1
for check in s:
    dp = [0] * 13
    for i in range(13):
        dp[(i * 10) % 13] = ans[i] % mod
    dp += dp
    for i in range(13):
        if check == '?':
            ans[i] = sum(dp[i + 4:i + 14])
        else:
            ans[i] = dp[i - int(check)]
print(ans[5] % mod)

Solution (Python):
inf = 10 ** 9 + 7
s = input()
n = len(s)
dp = [[0] * 13 for _ in range(n+1)]
dp[0][0] = 1
mul = 1

for i in range(n):
    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] %= inf
    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] %= inf
    mul = mul * 10 % 13
print(dp[n][5])

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

MOD = 10**9+7

dp = []

for i in range(N+1):
  dp.append([0]*13)

dp[0][0] =1

for i in range(1,N+1):
  for j in range(13):
    if S[i-1] == "?":
      for k in range(10):
        dp[i][(j*10+k) % 13] += dp[i-1][j]

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

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

Solution (Python):

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

"""
桁DPについて、S以下の数字で～の場合は
dp[i][j][k] : i桁目まで見たときに、その数字がSのj桁までより厳密に小さいか（一致する場合は0）、そこまでの値の13で割った時の値がkとなる個数（？をうめる方法の数）
といつもはしていたが、今回はSの中の？を埋める問題なので、jの厳密に一致するかどうかがいらない
なので、dp[i][j]は、i桁目まで見たときに、そこまでを13で割った時に13余るように？を決める方法の数
"""
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 num in range(10):
                dp[i+1][(10*j + num) % 13] += dp[i][j]
                dp[i+1][(10*j + num) % 13] %= MOD
        
        
        else:
            
            num = ord(S[i]) - ord("0")
            dp[i+1][(10*j + num) % 13] += dp[i][j]
            dp[i+1][(10*j + num) % 13] %= MOD


print(dp[-1][5])

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

Solution (Python):








S = input()
N = len(S)
S = S[::-1] 
dp = [[0] * 13 for i in range(N)]
if S[0] != "?":
  dp[0][int(S[0])] = 1 
else:
  for i in range(10):
    dp[0][i] = 1 
     

amari = [i for i in range(10)]

DIV = 10 ** 9 + 7




def update_amari():
  for i in range(len(amari)):
    amari[i] = (amari[i] * 10) % 13


for i in range(1,N):
  update_amari() 
  if S[i] == "?":
    
    
    for j in range(len(dp[i-1])):
      
      for k in amari:
        dp[i][(j + k) % 13] += dp[i-1][j]
        dp[i][(j + k) % 13] %= DIV
  else:
    
    for j in range(len(dp[i-1])):
      
      am = amari[int(S[i])]
      dp[i][(j + am) % 13] += dp[i-1][j]
      dp[i][(j + am) % 13] %= DIV
        

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

Solution (Python):








S = input()
N = len(S)
S = S[::-1] 
dp = [[0] * 13 for i in range(N)]
if S[0] != "?":
  dp[0][int(S[0])] = 1 
else:
  for i in range(10):
    dp[0][i] = 1 
     

amari = [i for i in range(10)]
amarimap = {1:10,10:9,9:12,12:3,3:4,4:1,2:7,7:5,5:11,11:6,6:8,8:2,0:0}

DIV = 10 ** 9 + 7




def update_amari():
  for i in range(len(amari)):
    amari[i] = amarimap[amari[i]]


for i in range(1,N):
  update_amari() 
  if S[i] == "?":
    
    
    for j in range(len(dp[i-1])):
      
      for k in amari:
        dp[i][(j + k) % 13] += dp[i-1][j]
        dp[i][(j + k) % 13] %= DIV
  else:
    
    for j in range(len(dp[i-1])):
      
      am = amari[int(S[i])]
      dp[i][(j + am) % 13] += dp[i-1][j]
      dp[i][(j + am) % 13] %= DIV
        

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

Solution (Python):
S = input()
n = len(S)
p = 10**9+7
DP = [[0]*13 for i in range(n+1)]
DP[0][0] = 1
for i in range(1, n+1):
    for j in range(13):
        if S[i-1] == '?':
            DP[i][j] = sum([DP[i-1][(4*(j-k)) % 13] for k in range(10)]) % p
        else:
            k = int(S[i-1])
            DP[i][j] = DP[i-1][(4*(j-k)) % 13]
print(DP[n][5])

Solution (Python):

MOD = 10**9 + 7


def main():
    S = [s for s in input()[::-1]]
    N = len(S)
    dp = [[0]*13 for i in range(N+1)]
    dp[0][0] = 1
    d = 1
    for i in range(N):
        for j in range(13):
            if S[i] != "?":
                a = int(S[i])
                ne = ((a*d)+j) % 13
                dp[i+1][ne] += dp[i][j]
                dp[i+1][ne] %= MOD
            else:
                for k in range(10):
                    ne = ((k*d)+j) % 13
                    dp[i+1][ne] += dp[i][j]
                    dp[i+1][ne] %= MOD
        d *= 10
        d %= 13
    print(dp[N][5] % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
import sys,math,copy

def main():
    
    input = sys.stdin.readline
    S = ''.join(reversed(input().strip()))

    
    
    dp = [0] * 13
    dp_ = [0] * 13
    mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
    list10 = list(range(10))
    list13 = list(range(13))
    divisor = 10 ** 9 + 7
    dp_[0] = 1
    mul = 1
    for i in range(len(S)):
        s = S[i]
        if s == '?':
            for d in list10:
                m = mod13_list[(d * mul)]
                for pm in list13:
                    dp[mod13_list[(pm+m)]] += dp_[pm]

        else:
            si = int(s)
            m = mod13_list[(si * mul)]
            for pm in list13:
                dp[mod13_list[(pm+m)]] = dp_[pm]

        
        
        for j in list13:
            dp_[j] = dp[j] % divisor
            dp[j] = 0
        mul = mod13_list[(mul * 10)]
    print(dp_[5])

if __name__ == '__main__':
    main()