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$.