import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines p,_,*Q = map(int,read().split()) MOD = 10**9 + 7 U = 2 * 10 ** 6 + 10 A = [0] * U a,b,c,d = 2*p, 2-p*p, -2*p, -1 a,b,c,d = map(lambda x: x%MOD, [a,b,c,d]) A[2] = 1 A[3] = (2*p)%MOD for n in range(4,U): A[n] = a*A[n-1] + b*A[n-2] + c*A[n-3] + d*A[n-4] A[n] %= MOD for q in Q: print(A[q-2])