题目背景

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：灵空

$样例不是出题人写的！！！！！！！！$