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):


modulous=10**9+7
r=[[(j-i)*4%13 for i in range(10)]for j in range(13)]
d=[1]+[0]*12
for c in input():
  if c>"9":
    d=[(sum(d[i] for i in j))%modulous for j in r]
  else:
    d=[d[((j-int(c))*4%13)] for j in range(13)]
    
print(d[5])

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
from itertools import permutations,  combinations, accumulate
from functools import *
from collections import deque, defaultdict, Counter
from heapq import heapify, heappop, heappush, heappushpop

INF = float('inf')
NIL = - 1
MOD = 10 ** 9 + 7


S = input().rstrip()
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])

Solution (Python):
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 m in range(13):
            idx= (m+b)%13
            dp[idx]= tmp[m]
    
    if j==5: j=0
    else: j+=1

print(dp[5])

Solution (Python):


import sys



















def main():
    mod = 1000000007                  
    inf = float('inf')
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    s = input()
    n = len(s)
    s = list(reversed(s))
    determined = 0    
    
    
    L = []
    for i in range(n):
        if s[i] != '?':
            determined += pow(10, i, 13) * int(s[i])
            determined %= 13
        else:
            L.append(pow(10, i, 13))
    
    
    
    target_res = ((13+5) - determined) % 13
    m = len(L)
    if m == 0:
        print(1) if target_res == 0 else print(0)
    else:
        
        dp = [[0] * 13 for _ in range(m)]
        first_line = [(L[0] * x) % 13 for x in range(10)]
        for j in range(13):
            dp[0][j] = first_line.count(j)
        for i in range(1, m):
            for j in range(13):
                elm = L[i]
                for x in range(10):
                    tmp = (x * elm) % 13
                    j_prime = (j + 13 - tmp) % 13
                    dp[i][j] += dp[i-1][j_prime]
                    dp[i][j] %= mod
        print(dp[m-1][target_res])

    

if __name__ == "__main__":
    main()

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

mod = 10**9+7


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

if s[0] == "?":
    for i in range(10):
        dp[0][i%13] += 1
else:
    dp[0][int(s[0])%13] += 1

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

Solution (Python):
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])

Solution (Python):

def inputlist(): return [int(k) for k in input().split()]

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

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

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

dp = [1] + [0] * 12
for c in s:
  tmp = dp[:]
  if c == '?':
    dp = [0] * 13
    for n in range(10):
      for i in range(13):
        index = (10 * i + n) % 13
        dp[index] = (dp[index] + tmp[i]) % mod
  else:
    n = int(c)
    for i in range(13):
      dp[(10 * i + n) % 13] = tmp[i]
print(dp[5])

Solution (Python):
mod=10**9+7
S=input()
dp=[0]*13
dp[0]=1

for s in S:
    prev=[x for x in dp]
    dp=[0]*13
    if s=='?':
        nx=range(10)
    else:
        nx=[int(s)]
    for i in range(13):
        for j in nx:
            dp[(10*i+j)%13]+=prev[i]
    dp=[x%mod for x in dp]
print(dp[5])

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

if __name__ == "__main__":
    main()

Solution (Python):
s=input()
n=len(s)
arr=[]
cnt=0
mod=10**9+7
rem=[1,10,9,12,3,4]
for i in reversed(range(n)):
  if s[i]=='?':
    arr.append(rem[(n-i)%6-1])
  else:
    cnt+=rem[(n-i)%6-1]*int(s[i])
    cnt%=13


if arr:
  m=len(arr)
  dp=[[0]*13 for _ in range(m)]
  for i in range(10):
    dp[0][i*arr[0]%13]+=1
  for i in range(1,m):
    for j in range(13):
      for k in range(10):
        dp[i][(k*arr[i]+j)%13]+=dp[i-1][j]
        dp[i][(k*arr[i]+j)%13]%=mod
  
  for i in range(13):
    if (cnt+i)%13==5:
      print(dp[m-1][i]%mod)
      exit()
else:
  if cnt==5:
    print(1)
  else:
    print(0)

Solution (Python):
import sys
readline = sys.stdin.readline

def main():

	
	s = input()
	length = len(s)

	dp = [[0]*13 for _ in range(length)]
	MOD = 10**9+7
	if s[-1] == '?':
		for i in range(10):
			dp[0][i] = 1
	else:
		dp[0][int(s[-1])] = 1

	num = 1
	for i in range(1,length):
		num = (10*num) % 13
		if s[-i-1] != '?':
			num2 = num * int(s[-i-1]) % MOD
			for j in range(13):
				dp[i][(num2+j)%13] = dp[i-1][j] % MOD
		else:
			for j in range(10):
				for k in range(13):
					dp[i][(num*j+k)%13] += dp[i-1][k] % MOD

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

if __name__ == '__main__':
	main()

Solution (Python):
def main():
	import sys
	readline = sys.stdin.readline

	
	s = input().rstrip()
	n = len(s)

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

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

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

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

if __name__ == '__main__':
	main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline

    mod = 10**9 + 7

    s = input().rstrip()
    n = len(s)
    dp = [[0]*13 for _ in range(n)]

    if s[-1]=='?':
        for i in range(10):
            dp[0][i] = 1
    else:
        a = int(s[-1])
        dp[0][a] = 1

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


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby
    
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    

    
    mod = 10**9 + 7

    s = input().rstrip()
    n = len(s)
    dp = [[0]*13 for _ in range(n)]

    if s[-1]=='?':
        for i in range(10):
            dp[0][i] = 1
    else:
        a = int(s[-1])
        dp[0][a] = 1

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys













readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    s = input()
    d = len(s)

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

    x = s[0]
    if x == "?":
        for i in range(10):
            nummod = (i * pow(10, d - 1, 13)) % 13
            dp[0][nummod] = 1
    else:
        nummod = (int(x) * pow(10, d - 1, 13)) % 13
        dp[0][nummod] = 1

    for i in range(1, d):
        x = s[i]
        if x == "?":
            for j in range(10):
                nummod = (j * pow(10, d - i - 1, 13)) % 13
                for k in range(13):
                    count = dp[i - 1][k]
                    nextmod = (k + nummod) % 13
                    dp[i][nextmod] += count
                    dp[i][nextmod] = dp[i][nextmod] % MOD
        else:
            nummod = (int(x) * pow(10, d - i - 1, 13)) % 13
            for j in range(13):
                count = dp[i - 1][j]
                nextmod = (j + nummod) % 13
                dp[i][nextmod] += count
                dp[i][nextmod] = dp[i][nextmod] % MOD

    print(dp[-1][5])


if __name__ == '__main__':
    main()

Solution (Python):
S = list(input())[::-1]
N = len(S)
B = [10**i % 13 for i in range(6)]

dp = [[0]*13 for i in range(N+2)]
dp[0][0] = 1
for i in range(1,N+1):
    if S[i-1] == '?':
        for j in range(10):
            for k in range(13):
                dp[i][(k+(B[(i-1)%6]*j))%13] += dp[i-1][k]
                dp[i][(k+(B[(i-1)%6]*j))%13] %= 10**9+7
    else:
        for k in range(13):
            dp[i][(k+B[(i-1)%6]*int(S[i-1]))%13] = dp[i-1][k]
print(dp[N][5])

Solution (Python):
s = input()

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

dp[0][0] = 1

for i in range(len(s)):
    ch = s[i]
    if ch == '?':
        for j in range(13):
            for k in range(10):
                dp[i+1][(10*j+k)%13] += dp[i][j]
                dp[i+1][(10*j+k)%13] %= 10 ** 9 + 7
    else:
        val = int(ch)
        for j in range(13):
            dp[i+1][(10*j+val)%13] += dp[i][j]
            dp[i+1][(10*j+val)%13] %= 10 ** 9 + 7

print(dp[-1][5])

Solution (Python):
import sys,math,copy

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

    
    
    dp = [0] * 13
    dp_ = [0] * 13
    mod13_tuple = tuple([i % 13 for i in range(12 ** 2 + 1)])
    tuple10 = tuple(range(10))
    tuple13 = tuple(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 tuple10:
                m = mod13_tuple[(d * mul)]
                for pm in tuple13:
                    dp[mod13_tuple[(pm+m)]] += dp_[pm]

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

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

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])

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()

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  s=S()
  n=len(s)

  dp=[[0]*13 for _ in range(n+1)]
  dp[0][0]=1
  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]
    
    else:
      a=int(s[i])
      for j in range(13):
        dp[i+1][(j*10+a)%13]+=dp[i][j]

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

  return dp[n][5]


print(main())

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

for i in range(N):
    if S[i] == "0":
        k += 1
    else:
        break

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

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

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

s = input()
n = len(s)

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

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

Solution (Python):
import sys













readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    s = input()
    d = len(s)

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

    x = s[0]
    if x == "?":
        for i in range(10):
            nummod = (i * pow(10, d - 1, 13)) % 13
            dp[0][nummod] = 1
    else:
        nummod = (int(x) * pow(10, d - 1, 13)) % 13
        dp[0][nummod] = 1

    for i in range(1, d):
        x = s[i]
        if x == "?":
            for j in range(10):
                nummod = (j * pow(10, d - i - 1, 13)) % 13
                for k in range(13):
                    count = dp[i - 1][k]
                    nextmod = (k + nummod) % 13
                    dp[i][nextmod] += count
                    dp[i][nextmod] = dp[i][nextmod] % MOD
        else:
            nummod = (int(x) * pow(10, d - i - 1, 13)) % 13
            for j in range(13):
                count = dp[i - 1][j]
                nextmod = (j + nummod) % 13
                dp[i][nextmod] += count
                dp[i][nextmod] = dp[i][nextmod] % MOD

    print(dp[-1][5])


if __name__ == '__main__':
    main()

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

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

a=1
for i in range(1,len_s):
    a=10*a%13
    if s[-(i+1)]!='?':
        temp_S=int(s[-(i+1)])
        amari=(temp_S*a)%13
        for j in range(13):
            dp[i][(amari+j)%13]+=dp[i-1][j]%mod

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

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

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

    c = -1 if s[i] == '?' else int(s[i])
    for j in range(10):
        if c != -1 and c != j:
            continue
        for r in range(13):
            dp[i+1][(10*r+j)%13] += dp[i][r]
    for k in range(13):
        dp[i+1][k] %= MOD
print(dp[l][5])

Solution (Python):
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left

def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]


def main():
    S = input()
    S = [int(i) if not i == "?" else False for i in S]
    

    S.reverse()


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

    kake = 4
    for keta, s in enumerate(S, 1):
        kake *= 10
        kake %= 13
        

        if s is not False:
            for i in range(13):
                idx = (i + kake * s) % 13
                dp[keta][idx] += dp[keta-1][i]

        else:
            for i in range(13):
                for j in range(10):
                    idx = (i + kake * j) % 13
                    dp[keta][idx] += dp[keta-1][i]
                    dp[keta][idx] %= mod

    
    
    

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


def solve():
    N, M = iip(True)
    lines = {}
    for i in range(N):
        lines[i] = []

    for i in range(M):
        a, b = iip(True)
        lines[a-1].append(b-1)
        lines[b-1].append(a-1)

    c = [[0]]
    for a in range(1, N):
        n = []
        for i in c:
            for j in range(N):
                if j in i:
                    continue
                ct = [k for k in i]
                ct.append(j)
                n.append(ct)
        c = n

    kh = []
    for i in c:
        for j in range(N):
            if j not in i:
                break
        else:
            kh.append(i)

    ans = 0
    for root in kh:
        for i in range(N):
            if i == N-1:
                ans += 1
                break
            else:
                if not root[i+1] in lines[root[i]]:
                    break

    print(ans)



def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Solution (Python):
mod=10**9+7
s=input()
dp1=[1]+[0]*12
for i in range(len(s)):
    dp2=[0]*13
    if s[i]!='?':
        p=int(s[i])
        for j in range(13):
            dp2[(j*10+p)%13]+=dp1[j]
    else:
        for p in range(10):
            for j in range(13):
                dp2[(j*10+p)%13]+=dp1[j]
    dp1=[dp2[j]%mod for j in range(13)]
print(dp1[5])

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

dp = [[0] * 13 for _ in range(2)]
tmp = 0
for si in s:
    if(si != '?'):
        tmp = (tmp*10 + int(si)) % 13
    else:
        tmp = tmp*10 % 13

dp[0][tmp] = 1
exp10 = 1
pointer = 0
for i,si in enumerate(s[::-1]):

    if(si!='?'):
        exp10 = exp10 * 10 % 13
        continue

    pointer = 1 - pointer
    for j in range(13):
        dp[pointer][j] = 0

    for j in range(13):
        for k in range(10):
            dp[pointer][(j + exp10*k)%13] += dp[1-pointer][j]

    for j in range(13):
        dp[pointer][j] %= mod

    exp10 = exp10 * 10 % 13

print(dp[pointer][5])

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
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][(k*mul+j)%13] += dp[i][j]
                dp[i+1][(k*mul+j)%13] %= mod
    else:
        k = int(x)
        for j in range(13):
            dp[i+1][(k*mul+j)%13] += dp[i][j]
            dp[i+1][(k*mul+j)%13] %= mod
    mul = mul*10%13
print (dp[n][5])

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

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] %= 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[len(S)][5])

Solution (Python):
mod=10**9+7
s=input()
dp1=[1]+[0]*12
for i in range(len(s)):
    dp2=[0]*13
    if s[i]!="?":
        p=int(s[i])
        for j in range(13):
            dp2[(j*10+p)%13]+=dp1[j]
    
    else:
        for p in range(10):
            for j in range(13):
                dp2[(j*10+p)%13]+=dp1[j]
    dp1=[dp2[j]%mod for j in range(13)]

print(dp1[5])

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby
    
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    

    
    mod = 10**9 + 7

    s = input().rstrip()
    n = len(s)
    dp = [[0]*13 for _ in range(n)]

    if s[-1]=='?':
        for i in range(10):
            dp[0][i] = 1
    else:
        a = int(s[-1])
        dp[0][a] = 1

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


if __name__ == '__main__':
    main()

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,s in enumerate(S):
    for j in range(13):
        if(s=="?"):
            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))%13] += dp[i][j]
            dp[i+1][((j*10)+int(s))%13]%=mod
print(dp[l][5])

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

MOD = 10 ** 9 + 7
dp = [[0] * 13 for _ in range(10**5+10)]
dp[0][0] = 1
for i in range(L):
    j = -1 if S[i] == "?" else int(S[i])
    if j > -1:
        
        
        
        
        
        
        
        
        
        
        

        for ki in range(13):
            dp[i+1][(ki * 10 + j) % 13] += dp[i][ki]
    else:
        
        
        
        
        for j in range(10):
            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

print(dp[L][5])

Solution (Python):
S=input()
n=len(S)
R=[0]*13
cnt=[0]*13
Pow=[[] for i in range(6)]
mod=10**9+7

for i in range(6):
    c=10**i
    for j in range(10):
        Pow[i].append(c*j%13)
ans=0
flag=0
for i in range(n):
    if S[n-i-1]=="?":
        P=Pow[i%6]
        if flag==0:
            for p in P:
                R[p]=1
                flag=1
        else:
            for j in range(10):
                for k in range(13):
                    cnt[(k+P[j])%13]+=R[k]%mod
            R=cnt
            cnt=[0]*13
    else:
        x=int(S[n-i-1])
        ans+=Pow[i%6][x]
ans%=13
if flag==0:
    if ans==5:
        print(1)
    else:
        print(0)
else:
    print(R[(18-ans)%13]%mod)

Solution (Python):
S=input()[::-1]
l=len(S)
a=1
m=10**9+7
dp=[1]+[0]*12
for d in S:
    dp2=[0]*13
    if d=='?':
        for j in range(13):
            for k in range(10):
                dp2[(j+k*a)%13]+=dp[j]%m
    else:
        for j in range(13):
            dp2[(j+int(d)*a)%13]=dp[j]
    dp=dp2
    a=(a*10)%13 if a!=1 else 10
print(dp[5]%m)

Solution (Python):
s = input()

frommap = []
for d in range(10):
    frommap.append([0] * 13)
    for m in range(13):
        m2 = (m * 10 + d) % 13
        frommap[d][m2] = m
transmap = list(zip(*frommap))

dp = [1] + [0] * 12
for c in s:
    if c == '?':
        dp = [sum(dp[f] for f in fromlist) % 1000000007 for fromlist in transmap]
    else:
        dp = [dp[f] for f in frommap[int(c)]]

print(dp[5])

Solution (Python):
s = input()

frommap = []
for d in range(10):
    frommap.append([0] * 13)
    for m in range(13):
        m2 = (m * 10 + d) % 13
        frommap[d][m2] = m
transmap = list(zip(*frommap))

dp = [1] + [0] * 12
for c in s:
    if c == '?':
        dp = [sum(dp[f] for f in fromlist) % 1000000007 for fromlist in transmap]
    else:
        dp = [dp[f] for f in frommap[int(c)]]

print(dp[5])

Solution (Python):
s = input()

frommap = []
for d in range(10):
    frommap.append([0] * 13)
    for m in range(13):
        m2 = (m * 10 + d) % 13
        frommap[d][m2] = m

dp = [1] + [0] * 12
for c in s:
    if c == '?':
        dp = [sum(dp[f] for f in fromlist) % 1000000007 for fromlist in zip(*frommap)]
    else:
        dp = [dp[f] for f in frommap[int(c)]]

print(dp[5])

Solution (Python):
s = input()

frommap = []
for d in range(10):
    frommap.append([0] * 13)
    for m in range(13):
        m2 = (m * 10 + d) % 13
        frommap[d][m2] = m

dp = [1] + [0] * 12
for c in s:
    if c == '?':
        dp = [sum(dp[f] for f in fromlist) % 1000000007 for fromlist in zip(*frommap)]
    else:
        dp = [dp[f] for f in frommap[int(c)]]

print(dp[5])

Solution (Python):
s = input()

frommap = []
for d in range(10):
    frommap.append([0] * 13)
    for m in range(13):
        m2 = (m * 10 + d) % 13
        frommap[d][m2] = m

dp = [1] + [0] * 12
for c in s:
    if c == '?':
        dp = [sum(dp[f] for f in fromlist) % 1000000007 for fromlist in zip(*frommap)]
    else:
        f = frommap[int(c)]
        dp = [dp[f[m]] for m in range(13)]

print(dp[5])

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(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]
        dp[i][(j*10+k)%13]%=mod
    else:
      dp[i][(j*10+int(s[i-1]))%13]+=dp[i-1][j]
      dp[i][(j*10+int(s[i-1]))%13]%=mod
print(dp[n][5])