CF1548C The Three Little Pigs

来自世界各地的三只小猪正在参加一次大会！每分钟，都会有一组三只新小猪到达会场。在第 $n$ 分钟后，大会结束。 大灰狼得知了这次大会，并制定了一个袭击计划。在大会的某一分钟，他会出现并恰好吃掉 $x$ 只小猪。然后他就会离开。 大灰狼想让 Gregor 帮他计算，在吃掉恰好 $x$ 只小猪的情况下，有多少种不同的袭击计划（对于不同的 $x$，$1 \le x \le 3n$）。如果袭击发生的时间不同，或者被吃掉的小猪集合不同，则认为两种袭击计划是不同的。 注意，所有的询问都是独立的，也就是说，大灰狼并不会真的吃掉小猪，他只是做计划！

输入的第一行包含两个整数 $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$ 后输出。

在示例测试中，$n=2$。因此，第 $1$ 分钟有 $3$ 只小猪，第 $2$ 分钟有 $6$ 只小猪。共有三次询问：$x=1$、$x=5$ 和 $x=6$。 如果大灰狼想吃 $1$ 只小猪，他可以在第 $1$ 分钟或第 $2$ 分钟行动，共有 $3+6=9$ 种不同的袭击计划，取决于他选择哪一分钟。 如果大灰狼想吃 $5$ 只小猪，他不能在第 $1$ 分钟行动，因为那时没有足够的小猪。因此，他只能在第 $2$ 分钟行动，此时有 $6$ 种不同的袭击计划。 如果大灰狼想吃 $6$ 只小猪，他唯一的计划是在大会结束时出现，把所有小猪都吃掉。 记得对每个答案取模 $10^9+7$ 后输出！ 由 ChatGPT 4.1 翻译