题目描述

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

输出格式

一个整数，表示答案。

3 5
1 2 4 5 0

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}$。