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):
S = input()
S = S[::-1]


mod = 10**9+7

dp = [0]*13
dp[0] = 1
for i in range(len(S)-1,-1,-1):
	ch = int(S[i]) if S[i]!='?' else -1
	temp = [0]*13
	for d in range(10):
		if ch!=-1 and ch!=d:
			continue
		for m in range(13):
			temp[(10*m+d)%13] += dp[m]
	for m in range(13):
		temp[m] %= mod
	dp = temp
print(dp[5])

Solution (Python):

mod=10**9+7
s=input()



rev=reversed(s)
d=[0 for i in range(13)]
d[0]=1
keep=[0 for _ in range(13)]
mul=1
cal=0
for v in rev:
    
    if v=="?":
        t_d=[0 for _ in range(13)]
        
        for k in range(0,13):
            for j in range(0,10):
                t_d[(mul*j+k)%13]+=d[k]
            t_d[k]%=mod
        d=t_d
    else:
        cal+=mul*int(v)%13
    mul*=10
    mul%=13
        
cal%=13
if cal<=5:
    cal=5-cal
else:
    cal=18-cal
print(d[cal]%mod)

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

Solution (Python):
import numpy as np
from numpy.fft import rfft, irfft
from itertools import cycle

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

mat = []
for i in range(6):
    w = np.zeros(13)
    for j in range(10):
        w[(10 ** i * j) % 13] += 1
    mat.append(rfft(w))

ress = [[(10 ** i * j) % 13 for j in range(10)] for i in range(6)]


state = np.zeros(13)
state[0] = 1
state = rfft(state)

res = 5
for keta, s in zip(cycle(range(6)), S[::-1]):
    if s == "?":
        state = state * mat[keta]
        if state[0] >= 2 ** 50:
            state = np.round(irfft(state, 13))
            state = rfft(np.remainder(state, mod))
    else:
        res -= ress[keta][int(s)]


state = irfft(state, 13)
print(int(np.round(state[res % 13])) % mod)

Solution (Python):
import numpy as np
from numpy.fft import rfft, irfft
from itertools import cycle

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

mat = []
for i in range(6):
    w = np.zeros(13)
    for j in range(10):
        w[(10 ** i * j) % 13] += 1
    mat.append(rfft(w))

ress = [[(10 ** i * j) % 13 for j in range(10)] for i in range(6)]


state = np.zeros(13)
state[0] = 1
state = rfft(state)

res = 5
for keta, s in zip(cycle(range(6)), reversed(S)):
    if s == "?":
        state = state * mat[keta]
    else:
        res -= ress[keta][int(s)]

    if state[0] >= 2 ** 50:
        state = np.round(irfft(state, 13))
        state = rfft(np.remainder(state, mod))


state = irfft(state, 13)
print(int(np.round(state[res % 13])) % mod)

Solution (Python):
import numpy as np
from numpy.fft import rfft, irfft

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

mat = []
for i in range(6):
    w = np.zeros(13)
    for j in range(10):
        w[(10 ** i * j) % 13] += 1
    mat.append(rfft(w))

ress = [[(10 ** i * j) % 13 for j in range(10)] for i in range(6)]


state = np.zeros(13)
state[0] = 1
state = rfft(state)

keta = 0
res = 5
for s in reversed(S):
    if s == "?":
        state = state * mat[keta % 6]
    else:
        res -= ress[keta % 6][int(s)]

    if state[0] >= 2 ** 50:
        state = np.round(irfft(state, 13))
        state = rfft(np.remainder(state, mod))

    keta += 1

state = irfft(state, 13)
print(int(np.round(np.real(state[res % 13]))) % mod)

Solution (Python):

N = input()
digit = len(N)
mod = 1000000007


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

d = 1/10
for i in range(digit-1,-1,-1):
  ii = digit-i-1
  d = int((d*10)%13)
  for j in range(2):
    for k in range(13):
      if N[i] == "?":
        for n in range(9+1):
          dp[ii+1][j][(k + n*d) %13] += dp[ii][j][k] %mod
      else:
        n = int(N[i])
        dp[ii+1][j][(k + n*d) %13] += dp[ii][j][k] %mod

print((dp[digit][0][5] + dp[digit][1][5]) %mod)