题目内容

给定一个正整数 $m$，定义一个数列 $\{a_n\}$：前 $m$ 项均为 $1$，即 $a_1 = a_2 = \dots = a_m = 1$；对于 $n > m$，第 $n$ 项等于它前面 $m$ 项的和，即 $a_n = a_{n-1} + a_{n-2} + \dots + a_{n-m}$。现在有 $t$ 次询问，每次询问给出一个正整数 $x$，你需要输出 $a_x$ 对 $10^9+7$ 取模的结果。

数据范围：$1 \le m \le 10^6$，$1 \le t \le 2 imes 10^5$，$1 \le x \le 10^6$。

输入描述

第一行包含两个整数 $m$ 和 $t$，分别表示数列跨度和询问次数。 接下来 $t$ 行，每行包含一个整数 $x$，表示查询的项数。

输出描述

输出 $t$ 行，每行一个整数，表示对应询问的答案模 $10^9+7$。

样例1

输入

1 3
1
2
3

输出

1
1
1

说明

当 $m = 1$ 时，数列满足 $a_1 = 1$，且对于 $n > 1$ 有 $a_n = a_{n-1}$。因此所有项均为 1。查询 1、2、3 时输出 1。

样例2

输入

3 3
1
4
6

输出

1
3
9

说明

当 $m = 3$ 时，前 3 项均为 1：$a_1 = a_2 = a_3 = 1$。 计算后续项： $a_4 = a_1 + a_2 + a_3 = 1 + 1 + 1 = 3$； $a_5 = a_2 + a_3 + a_4 = 1 + 1 + 3 = 5$； $a_6 = a_3 + a_4 + a_5 = 1 + 3 + 5 = 9$。 因此查询 $x = 1$ 输出 1，$x = 4$ 输出 3，$x = 6$ 输出 9。

样例3

输入

4 2
5
7

输出

4
13

说明

当 $m = 4$ 时，前 4 项均为 1：$a_1 = a_2 = a_3 = a_4 = 1$。 计算后续项： $a_5 = a_1 + a_2 + a_3 + a_4 = 4$； $a_6 = a_2 + a_3 + a_4 + a_5 = 1 + 1 + 1 + 4 = 7$； $a_7 = a_3 + a_4 + a_5 + a_6 = 1 + 1 + 4 + 7 = 13$。 因此 $x = 5$ 输出 4，$x = 7$ 输出 13。