Fancy 배열

정수 $m$을 하나 정하자. 양의 정수 $n$개로 이루어진 배열 $a$를 생각한다. $a$의 모든 원소가 $m$의 약수이고, 이웃한 두 원소가 서로소가 아니면 $a$를 fancy 배열이라고 한다.

길이가 $n$인 fancy 배열의 개수를 구하라. 개수가 클 수 있으므로 $10^{9} + 7$로 나눈 나머지를 구한다.

첫 줄에 정수 $m$과 $q$가 주어진다. $m$은 위에서 정의한 수이고, $q$는 질의의 개수이다 ($1 \le m \le 10^{16}$, $1 \le q \le 150$).

이어지는 $q$개의 줄에 각각 정수 $n$이 하나씩 주어진다 ($1 \le n \le 10^{18}$).

각 질의마다 주어진 $m$과 $n$에 대한 길이 $n$의 fancy 배열 개수를 $10^{9} + 7$로 나눈 나머지로 한 줄에 출력한다.