T, M = map(int, input().split())
MAX_N = 5*10**6+10
rot4 = [0]*MAX_N
rot2 = [0]*MAX_N
rot2_sym = [0]*MAX_N
sym = [0]*MAX_N
fact = [0]*MAX_N

rot4[4] = 2
for i in range(8, MAX_N, 4):
    rot4[i] = rot4[i-4]*(i-2) % M
for i in range(5, MAX_N, 4):
    rot4[i] = rot4[i-1]

rot2_sym[2] = 2
rot2_sym[4] = 6
for i in range(6, MAX_N, 2):
    rot2_sym[i] = (2*rot2_sym[i-2]+(i-2)*rot2_sym[i-4]) % M
for i in range(3, MAX_N, 2):
    rot2_sym[i] = rot2_sym[i-1]

rot2[2] = 2
for i in range(4, MAX_N, 2):
    rot2[i] = i*rot2[i-2] % M
for i in range(3, MAX_N, 2):
    rot2[i] = rot2[i-1]

sym[1] = 1
sym[2] = 2
for i in range(3, MAX_N):
    sym[i] = (sym[i-1]+(i-1)*sym[i-2]) % M

fact[0] = 1
for i in range(1, MAX_N):
    fact[i] = i*fact[i-1] % M

for _ in range(T):
    N = int(input())
    if N == 1:
        print(1 % M)
        continue
    c2 = rot4[N]
    c3 = rot2_sym[N]
    c4 = (rot2[N]-rot2_sym[N]-rot4[N]) % M
    c5 = (sym[N]-rot2_sym[N]) % M
    c6 = c5
    c7 = (fact[N]-c2-c3-c4-c5-c6) % M
    ans = (c2*2+c3*2+c4*4+c5*4+c6*4+c7*8) % M
    print(ans)