Description

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.

Input Format

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

Output Format

One integer, the answer.

3 5
1 2 4 5 0

44044

Hint

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