p = int(input())
mod = 10**9+7
q = int(input())
Q = [int(input()) for i in range(q)]
A = [0,0,1]
S = [0,0,0]
M = 2*10**6+5
for i in range(3,M):
    A.append((p*A[-1]+A[-2])%mod)
    S.append(((i-3)*A[-3]-S[-2])%mod)

for q in Q:
    print(S[q])