24676번 - Fancy Arrays 다국어

문제

Let us fix an integer $m$. Consider an array $a$ consisting of $n$ positive integers. The array $a$ is fancy if each number in $a$ is a divisor of $m,ドル and each two neighboring numbers in $a$ are not coprime.

Find the total number of fancy arrays of length $n$. As the answer may be large, find it modulo 10ドル^{9} + 7$.

입력

The first line contains two integers, $m$ and $q$: the number introduced above and the number of queries (1ドル \le m \le 10^{16},ドル 1ドル \le q \le 150$).

Each of the next $q$ lines contains a single integer $n$ (1ドル \le n \le 10^{18}$).

출력

For each query, print the number of fancy arrays for the given $m$ and $n$ modulo 10ドル^{9} + 7$.

제한

힌트