Geometric Series LCM

Koishi truly loves number theory. To test her passion, her friend Flandre has given her the following problem.

Define the function \( f(n)=\sum_{i=0}^{n} x^i \). Given an integer \( x \) and \( N \) integers \( a_1,a_2,\dots,a_N \), you are to compute \[ \mathrm{lcm}(f(a_1),f(a_2),\dots,f(a_N)) \mod (10^9+7), \] where lcm denotes the least common multiple.

Note that when \( x=1 \), we have \( f(n)=n+1 \), and for \( x\neq1 \), the closed form is given by \[ f(n)=\frac{x^{n+1}-1}{x-1}. \]

Please help Koishi solve the problem within 1 second.

inputFormat

The first line contains two integers: \( x \) and \( N \) (the number of queries).

The second line contains \( N \) space‐separated integers \( a_1,a_2,\dots,a_N \).

outputFormat

Output a single integer, the value of \( \mathrm{lcm}(f(a_1),f(a_2),\dots,f(a_N)) \mod (10^9+7) \).

sample

1 3
1 2 3

12