# https://stackoverflow.com/questions/65017966/given-n-find-how-many-n-digit-numbers-are-there-such-that-the-number-has-prime/65020994?noredirect=1#comment114995029_65020994

n = 2
m = 4
k = 0
primes = [2,3,5,7]
non_primes = [1,4,6,8,9]

row = [2, 2, 1, 0]

# (1) Transform the current row of remainders,
# each storing a count, multiplying by 10:

new_row = [0] * m

for r in range(m):
    new_r = (10 % m * r) % m
    new_row[new_r] += row[r]
  
row = new_row

print(row)
    
# (2) Create new counts by using the new
# possible digits:

i = 2
new_row = [0] * m
for d in (primes if i in primes else non_primes):
    for r in range(m):
      new_r = (r + d) % m
      new_row[new_r] += row[r]

row = new_row

print(row)