← 返回题目列表

Codeforces · 1548/C

C. 三只小猪

中文机器翻译题面 查看原题

来自世界各地的三只小猪正在开会!每分钟,就会有三只新猪到达会议场地。第 $$$n$$$ 分钟后,大会结束。

大灰狼已经了解了这个约定,并且他有了一个攻击计划。在大会的某个时刻,他会到达并吃掉 $$$x$$$ 的猪。然后他就会逃脱。

狼希望 Gregor 帮助他计算出可能的攻击计划的数量,这些计划涉及在不同的 $$$x$$$ 值($$$1 \le x \le 3n$$$)下精确吃掉 $$$x$$$ 头猪。如果两个攻击计划发生在不同的时间或者吃的小猪不同,则它们被认为是不同的。

注意,所有查询都是独立的,也就是说,狼不吃小猪,他只制定计划!

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n \le 10^6$$$, $$$1 \le q \le 2\cdot 10^5$$$),约定持续的分钟数以及狼询问的查询数。

接下来的 $$$q$$$ 行包含一个整数 $$$x_i$$$ ($$$1 \le x_i \le 3n$$$),狼在第 $$$i$$$ 查询中将吃掉的猪的数量。

输出

你应该打印 $$$q$$$ 行,其中 $$$i$$$ 行代表如果狼想吃掉 $$$x_i$$$ 猪的话攻击计划的数量。由于每个查询答案可能很大,因此输出每个答案对 $$$10^9+7$$$ 取模。

示例

输入 #1

2 3
1
5
6

输出 #1

9
6
1

输入 #2

5 4
2
4
6
8

输出 #2

225
2001
6014
6939

注意

在示例测试中,$$$n=2$$$。因此,在$$$1$$$分钟有$$$3$$$猪,在$$$2$$$分钟有$$$6$$$猪。共有三个查询:$$$x=1$$$、$$$x=5$$$ 和 $$$x=6$$$。

如果狼想吃掉 $$$1$$$ 猪,他可以在 $$$3+6=9$$$ 可能的攻击计划中这样做,具体取决于他是在 $$$1$$$ 分钟还是 $$$2$$$ 到达。

如果狼想吃掉 $$$5$$$ 猪,那么狼无法在 $$$1$$$ 分钟到达,因为当时没有足够的猪。因此,狼必须在$$$2$$$分钟到达,并且有$$$6$$$可能的攻击计划。

如果狼想吃掉 $$$6$$$ 猪,他唯一的计划就是在大会结束时到达并吞噬所有人。

请记住以 $$$10^9+7$$$ 为模输出你的答案!