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