来自世界各地的三只小猪正在开会!每分钟,就会有三只新猪到达会议场地。第 $$$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$$$ 为模输出你的答案!