Koishi Loves Number Theory
题目描述
Koishi 十分喜欢数论。
她的朋友 Flandre 为了检测她和数论是不是真爱，给了她一个问题。
已知 $f(n)=\sum_{i=0}^nx^i$
给定 $x$ 和 $N$ 个数 $a_i$，求 $\mathrm{lcm}(f(a_1),f(a_2),...,f(a_N))$ 对 $10^9+7$ 取模。
按照套路，呆萌的 Koishi 当然假装不会做了，于是她来向你请教这个问题，希望你能在 $1$ 秒内给她答案。
输入输出格式
输入格式
第一行包含两个整数 $x$ 和 $N$，接下来一行 $N$ 个整数表示 $a_i$。
输出格式
一个整数，表示答案。
输入输出样例
输入样例 #1
3 5
1 2 4 5 0输出样例 #1
44044说明
$\mathrm{lcm}$ 表示若干个数的**最小公倍数**。
对于 $10\%$ 的数据，$1\leq N\leq 100$，$0\leq a_i\leq 9$，$x=2$。
对于另外 $20\%$ 的数据，$1\leq N\leq 50$，$0\leq a_i\leq 100$，$2\leq x\leq 10$。
对于另外 $30\%$ 的数据，$1\leq N\leq 16$，$0\leq a_i\leq 10^9$，$2\leq x\leq 10^{18}$。
对于 $100\%$ 的数据，$1\leq N\leq 100$，$0\leq a_i\leq 10^9$，$2\leq x\leq 10^{18}$，且 $x\not\equiv 1\pmod{10^9+7}$。