Problem: 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.

Submission attempts (in order):
def dot(A, x):
  return [sum([x[t]*A[s][t] for t in range(13)]) for s in range(13)]

S=input()
N=len(S)
if N==1:
  if S=='?' or int(S)==5:
    print(1)
  else:
    print(0)
  exit()

MOD=10**9+7

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

for i in range(1, N):
  if S[i]=='?':
    tmp=sum(x)
    x=[
      tmp-x[4]-x[8]-x[12],
      tmp-x[3]-x[8]-x[12],
      tmp-x[3]-x[7]-x[12],
      tmp-x[3]-x[7]-x[11],
      tmp-x[2]-x[7]-x[11],
      tmp-x[2]-x[6]-x[11],
      tmp-x[2]-x[6]-x[10],
      tmp-x[1]-x[6]-x[10],
      tmp-x[1]-x[5]-x[10],
      tmp-x[1]-x[5]-x[9],
      tmp-x[0]-x[5]-x[9],
      tmp-x[0]-x[4]-x[9],
      tmp-x[0]-x[4]-x[8]
    ]
  elif S[i]=='0':
    x=[x[0], x[4], x[8], x[12], x[3], x[7], x[11], x[2], x[6], x[10], x[1], x[5], x[9]]
  elif S[i]=='1':
    x=[x[9], x[0], x[4], x[8], x[12], x[3], x[7], x[11], x[2], x[6], x[10], x[1], x[5]]
  elif S[i]=='2':
    x=[x[5], x[9], x[0], x[4], x[8], x[12], x[3], x[7], x[11], x[2], x[6], x[10], x[1]]
  elif S[i]=='3':
    x=[x[1], x[5], x[9], x[0], x[4], x[8], x[12], x[3], x[7], x[11], x[2], x[6], x[10]]
  elif S[i]=='4':
    x=[x[10], x[1], x[5], x[9], x[0], x[4], x[8], x[12], x[3], x[7], x[11], x[2], x[6]]
  elif S[i]=='5':
    x=[x[6], x[10], x[1], x[5], x[9], x[0], x[4], x[8], x[12], x[3], x[7], x[11], x[2]]
  elif S[i]=='6':
    x=[x[2], x[6], x[10], x[1], x[5], x[9], x[0], x[4], x[8], x[12], x[3], x[7], x[11]]
  elif S[i]=='7':
    x=[x[11], x[2], x[6], x[10], x[1], x[5], x[9], x[0], x[4], x[8], x[12], x[3], x[7]]
  elif S[i]=='8':
    x=[x[7], x[11], x[2], x[6], x[10], x[1], x[5], x[9], x[0], x[4], x[8], x[12], x[3]]
  elif S[i]=='9':
    x=[x[3], x[7], x[11], x[2], x[6], x[10], x[1], x[5], x[9], x[0], x[4], x[8], x[12]]
    
  x=[x[j]%MOD for j in range(13)]
    
print(x)

MOD=10**9+7
S=input()
N=len(S)
if N==1:
  if S=='?' or int(S)==5:
    print(1)
  else:
    print(0)
  exit()

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

for i in range(1, N):
  if S[i]=='?':
    tmp=sum(x)
    x=[
      tmp-x[4]-x[8]-x[12],
      tmp-x[3]-x[8]-x[12],
      tmp-x[3]-x[7]-x[12],
      tmp-x[3]-x[7]-x[11],
      tmp-x[2]-x[7]-x[11],
      tmp-x[2]-x[6]-x[11],
      tmp-x[2]-x[6]-x[10],
      tmp-x[1]-x[6]-x[10],
      tmp-x[1]-x[5]-x[10],
      tmp-x[1]-x[5]-x[9],
      tmp-x[0]-x[5]-x[9],
      tmp-x[0]-x[4]-x[9],
      tmp-x[0]-x[4]-x[8]
    ]
  elif S[i]=='0':
    x=[x[0], x[4], x[8], x[12], x[3], x[7], x[11], x[2], x[6], x[10], x[1], x[5], x[9]]
  elif S[i]=='1':
    x=[x[9], x[0], x[4], x[8], x[12], x[3], x[7], x[11], x[2], x[6], x[10], x[1], x[5]]
  elif S[i]=='2':
    x=[x[5], x[9], x[0], x[4], x[8], x[12], x[3], x[7], x[11], x[2], x[6], x[10], x[1]]
  elif S[i]=='3':
    x=[x[1], x[5], x[9], x[0], x[4], x[8], x[12], x[3], x[7], x[11], x[2], x[6], x[10]]
  elif S[i]=='4':
    x=[x[10], x[1], x[5], x[9], x[0], x[4], x[8], x[12], x[3], x[7], x[11], x[2], x[6]]
  elif S[i]=='5':
    x=[x[6], x[10], x[1], x[5], x[9], x[0], x[4], x[8], x[12], x[3], x[7], x[11], x[2]]
  elif S[i]=='6':
    x=[x[2], x[6], x[10], x[1], x[5], x[9], x[0], x[4], x[8], x[12], x[3], x[7], x[11]]
  elif S[i]=='7':
    x=[x[11], x[2], x[6], x[10], x[1], x[5], x[9], x[0], x[4], x[8], x[12], x[3], x[7]]
  elif S[i]=='8':
    x=[x[7], x[11], x[2], x[6], x[10], x[1], x[5], x[9], x[0], x[4], x[8], x[12], x[3]]
  elif S[i]=='9':
    x=[x[3], x[7], x[11], x[2], x[6], x[10], x[1], x[5], x[9], x[0], x[4], x[8], x[12]]
    
  x=[x[j]%MOD for j in range(13)]

print(x[5])

Verdicts: Wrong Answer

Accepted