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

IyBodHRwczovL3N0YWNrb3ZlcmZsb3cuY29tL3F1ZXN0aW9ucy82NTAxNzk2Ni9naXZlbi1uLWZpbmQtaG93LW1hbnktbi1kaWdpdC1udW1iZXJzLWFyZS10aGVyZS1zdWNoLXRoYXQtdGhlLW51bWJlci1oYXMtcHJpbWUvNjUwMjA5OTQ/bm9yZWRpcmVjdD0xI2NvbW1lbnQxMTQ5OTUwMjlfNjUwMjA5OTQKCm4gPSAyCm0gPSA0CmsgPSAwCnByaW1lcyA9IFsyLDMsNSw3XQpub25fcHJpbWVzID0gWzEsNCw2LDgsOV0KCnJvdyA9IFsyLCAyLCAxLCAwXQoKIyAoMSkgVHJhbnNmb3JtIHRoZSBjdXJyZW50IHJvdyBvZiByZW1haW5kZXJzLAojIGVhY2ggc3RvcmluZyBhIGNvdW50LCBtdWx0aXBseWluZyBieSAxMDoKCm5ld19yb3cgPSBbMF0gKiBtCgpmb3IgciBpbiByYW5nZShtKToKICAgIG5ld19yID0gKDEwICUgbSAqIHIpICUgbQogICAgbmV3X3Jvd1tuZXdfcl0gKz0gcm93W3JdCiAgCnJvdyA9IG5ld19yb3cKCnByaW50KHJvdykKICAgIAojICgyKSBDcmVhdGUgbmV3IGNvdW50cyBieSB1c2luZyB0aGUgbmV3CiMgcG9zc2libGUgZGlnaXRzOgoKaSA9IDIKbmV3X3JvdyA9IFswXSAqIG0KZm9yIGQgaW4gKHByaW1lcyBpZiBpIGluIHByaW1lcyBlbHNlIG5vbl9wcmltZXMpOgogICAgZm9yIHIgaW4gcmFuZ2UobSk6CiAgICAgIG5ld19yID0gKHIgKyBkKSAlIG0KICAgICAgbmV3X3Jvd1tuZXdfcl0gKz0gcm93W3JdCgpyb3cgPSBuZXdfcm93CgpwcmludChyb3cp