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 main():
  s = ''.join(reversed(input()))
  multiplier = 1
  divisor = 10 ** 9 + 7
  list10 = list(range(10))
  list13 = list(range(13))
  p = [0 for i in list13]
  np = [0 for i in list13]
  rt = [i % 13 for i in range(100)]
  if s[0] != '?':
    p[int(s[0])] = 1
  else:
    for j in range(10):
      p[j] = 1
  for i in range(1, len(s)):
    multiplier = (10 * multiplier) % 13
    if s[i] != '?':
      r = int(s[i]) * multiplier
      for j in list13:
        np[(j + r) % 13] = p[j]
    else:
      for j in range(10):
        r = multiplier * j % 13
        for k in list13:
          np[re[k + r]] += p[k]
    for j in list13:
      p[j] = np[j] % divisor
      np[j] = 0
  print(p[5] % divisor)
main()

def main():
  s = ''.join(reversed(input()))
  multiplier = 1
  divisor = 10 ** 9 + 7
  list10 = list(range(10))
  list13 = list(range(13))
  p = [0] * 13
  np = [0] * 13
  rt = [i % 13 for i in range(121)]
  p[0] = 1
  for i in range(len(s)):
    multiplier = rt[10 * multiplier]
    if s[i] != '?':
      r = rt[int(s[i]) * multiplier]
      for j in list13:
        np[rt[j + r]] = p[j]
    else:
      r = 0
      for j in list10:
        for k in list13:
          np[rt[k + r]] += p[k]
        r = rt[r + multiplier]
    for j in list13:
      p[j] = np[j] % divisor
      np[j] = 0
  print(p[5])
main()

def main():
  s = input()
  divisor = 10 ** 9 + 7
  lut = [i % 13 for i in range(133)]
  m = [i * 10 % 13 for i in range(10)]
  dp = [[0] * 13 for _ in range(len(s) + 1)]
  dp[0][0] = 1
  list10 = list(range(10))
  list13 = list(range(13))
  for i in range(len(s)):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    if s[i] == '?':
      for j in list10:
        for k in list13:
          dpi1[lut[m[k] + j]] += dpi[k]
    else:
      t = int(s[i])
      for k in list13:
        dpi1[lut[m[k] + t]] += dpi[k]
    for k in range(13):
      dpi1[k] %= divisor
  print(dp[len(s)][5])
main()


def main():
  s = ''.join(reversed(input()))
  multiplier = 1
  divisor = 10 ** 9 + 7
  list10 = list(range(10))
  list13 = list(range(13))
  p = [0 for i in list13]
  np = [0 for i in list13]
  rt = [i % 13 for i in range(120)]
  p[0] = 1
  for i in range(len(s)):
    multiplier = rt[10 * multiplier]
    if s[i] != '?':
      r = rt[int(s[i]) * multiplier]
      for j in list13:
        np[rt[j + r]] = p[j]
    else:
      r = 0
      for j in list10:
        for k in list13:
          np[rt[k + r]] += p[k]
        r = rt[r + multiplier]
    for j in list13:
      p[j] = np[j] % divisor
      np[j] = 0
  print(p[5])
main()

s = input()
s = [c for c in s]
s.reverse()
s = ''.join(s)
multiplier = 1
divisor = 10 ** 9 + 7
p = [0 for i in range(13)]
if s[0] != '?':
  p[int(s[0])] = 1
else:
  for j in range(10):
    p[j] = 1
for i in range(1, len(s)):
  print(','.join(map(str, p)))
  multiplier = (10 * multiplier) % 13
  if s[i] != '?':
    r = (int(s[i]) * multiplier) % 13
    np = [0 for j in range(13)]
    for j in range(len(p)):
      np[(j + r) % 13] = p[j]
    for j in range(13):
      p[j] = np[j]
  else:
    np = [0 for j in range(13)]
    for j in range(10):
      r = (j * multiplier) % 13
      for k in range(len(p)):
        np[(k + r) % 13] += p[k]
    for j in range(13):
      p[j] = np[j]
print(p[5] % divisor)


def main():
  s = input()
  divisor = 10 ** 9 + 7
  dp = [[0] * 13 for _ in range(len(s) + 1)]
  dp[0][0] = 1
  lut = [i % 13 for i in range(130)]
  list10 = list(range(10))
  list13 = list(range(13))
  for i in range(len(s)):
    dpi = dp[i]
    dpi1 = dp[i + 1]
    if s[i] == '?':
      j10 = 0
      for j in list13:
        dpij = dpi[j]
        for k in list10:
          dpi1[lut[j10 + k]] += dpij
        j10 += 10
    else:
      t = int(s[i])
      for j in list13:
        dpi1[t] += dpi[j]
        t = lut[t + 10]
    for k in list13:
      dpi1[k] %= divisor
  print(dp[len(s)][5])
main()


Verdicts: Runtime Error

Wrong Answer

Runtime Error

Runtime Error

Wrong Answer

Accepted