「MCOI-02」Build Battle 建筑大师

WAPER 爱玩 hypixel（世界上最大的 Minecraft 小游戏服务器） 建筑大师！ 提示：在本题中，羊毛属于一种方块。

现在 WAPER 准备玩 $q$ 局建筑大师。在第 $i$ 局游戏的开始，WAPER 会选定一个参数 $m_i$，并 **按顺序** 放置 $n$ 个有颜色的羊毛，羊毛颜色的排列如下： $$1,\ 2,\ ...\ ,\ m_i-1,\ m_i,\ 1,\ 2,\ ...\ ,m_i-1\ ,m_i\ ,\ ...\ (n-1) \ \bmod \ m_i+1$$ 例如 $n=7,m=3$ 时，颜色排列如下： $$1\ ,2,\ 3,\ 1,\ 2,\ 3,\ 1$$ 现在 WAPER 准备打破一些方块（可以一个也不打破，也可以全部打破），WAPER 想知道这样可以产生多少种不同的颜色序列。（两个颜色序列不同当且仅当其长度不同或某一位置的羊毛颜色不同） 因为答案太大，所以输出答案对 $10^9+7$ 取模的结果。 （其实就是询问这个序列本质不同的子序列对 $10^9+7$ 取模的结果）

第一行两个整数 $n$ 和 $q$ 代表羊毛数和局数。 第二行 $q$ 个整数 $m_i$ 代表参数。

$q$ 行，每行一个整数代表答案。 答案对 $10^9+7$ 取模。

10 6
1 1 4 5 1 4

11
11
833
944
11
833

1000000 1
114514

945636198

#### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（5 pts）$\ \ $：$n \le 20$，$q=1$。 - Subtask 2（15 pts）：$n \le 10^3$，$q=1$。 - Subtask 3（15 pts）：$\max\{m_i\} \le 20$，$q=1$。 - Subtask 4（25 pts）：$q=1$。 - Subtask 5（40 pts）：无特殊限制。 对于 $100\%$ 的数据，$1 \le n,q \le 10^6$，$1 \le m_i \le n$。 #### 说明 Minecraft OI Round 2 B - Maker：WAPER420 - Tester：灵空 $样例不是出题人写的！！！！！！！！$