p = int(input())
mod = 10**9+7

B = [1,(2*p) % mod,(3*p**2+2) % mod,(4*p**3+6*p) % mod]
for _ in range(2*10**6):
    B.append((2*p*B[-1]-(p**2-2)*B[-2]-2*p*B[-3]-B[-4]) % mod)

Q = int(input())
for _ in range(Q):
    q = int(input())
    if q <= 3:
        print(0)
    else:
        print(B[q-4])