import sys input = sys.stdin.readline mod=1000000007 p=int(input()) q=int(input()) Q=[int(input()) for i in range(q)] ANS=[0,0,0,0] A=[0,1] A.append(p*A[-1]+A[-2]) A.append(p*A[-1]+A[-2]) ANS[2]=(A[0]*A[2]*2+A[1]*A[1])%mod ANS[3]=(A[0]*A[3]*2+A[1]*A[2]*2)%mod for i in range(2*10**6): ANS.append((2*p*ANS[-1]-(p**2-2)*ANS[-2]-2*p*ANS[-3]-ANS[-4])%mod) for q in Q: print(ANS[q-2])