P3598 Koishi Loves Number Theory

Koishi loves number theory. Her friend Flandre, to check whether her love for number theory is true, gave her a problem. Given $f(n)=\sum_{i=0}^n x^i$. Given $x$ and $N$ numbers $a_i$, compute $\mathrm{lcm}(f(a_1),f(a_2),...,f(a_N))$ modulo $10^9+7$. As usual, the naive Koishi pretended she could not solve it and came to ask you, hoping you can give the answer within 1 second.

The first line contains two integers $x$ and $N$. The next line contains $N$ integers representing $a_i$.

One integer, the answer.

$\mathrm{lcm}$ denotes the least common multiple of several numbers. Constraints: - For $10\%$ of the testdata, $1 \leq N \leq 100$, $0 \leq a_i \leq 9$, $x=2$. - For another $20\%$ of the testdata, $1 \leq N \leq 50$, $0 \leq a_i \leq 100$, $2 \leq x \leq 10$. - For another $30\%$ of the testdata, $1 \leq N \leq 16$, $0 \leq a_i \leq 10^9$, $2 \leq x \leq 10^{18}$. - For $100\%$ of the testdata, $1 \leq N \leq 100$, $0 \leq a_i \leq 10^9$, $2 \leq x \leq 10^{18}$, and $x \not\equiv 1 \pmod{10^9+7}$. Translated by ChatGPT 5