CF1548C.The Three Little Pigs

Three little pigs from all over the world are meeting for a convention! Every minute, a triple of 3 new pigs arrives on the convention floor. After the $n$-th minute, the convention ends.

The big bad wolf has learned about this convention, and he has an attack plan. At some minute in the convention, he will arrive and eat exactly $x$ pigs. Then he will get away.

The wolf wants Gregor to help him figure out the number of possible attack plans that involve eating exactly $x$ pigs for various values of $x$ ($1 \le x \le 3n$). Two attack plans are considered different, if they occur at different times or if the sets of little pigs to eat are different.

Note that all queries are independent, that is, the wolf does not eat the little pigs, he only makes plans!

来自世界各地的三只小猪正在举行一场大会！每分钟，都会有三只新小猪组成的三元组抵达大会现场。在第 $n$ 分钟结束后，大会结束。

大野狼得知了这场大会，并制定了一个袭击计划：他将在大会期间的某一分钟抵达，并恰好吃掉 $x$ 只小猪，然后迅速逃离。

野狼希望格雷戈尔帮他计算出：对于不同的 $x$ 值（$1 \le x \le 3n$），有多少种可能的袭击计划恰好吃掉 $x$ 只小猪。若两个袭击计划发生的时间不同，或被吃掉的小猪集合不同，则视为不同的袭击计划。

注意：所有查询相互独立，即野狼并不会真正吃掉小猪，他只是在制定计划！

The first line of input contains two integers $n$ and $q$ ($1 \le n \le 10^6$, $1 \le q \le 2\cdot 10^5$), the number of minutes the convention lasts and the number of queries the wolf asks.

Each of the next $q$ lines contains a single integer $x_i$ ($1 \le x_i \le 3n$), the number of pigs the wolf will eat in the $i$-th query.

输入的第一行包含两个整数 $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$ 次查询中狼将要吃的猪的数量。

You should print $q$ lines, with line $i$ representing the number of attack plans if the wolf wants to eat $x_i$ pigs. Since each query answer can be large, output each answer modulo $10^9+7$.

你需要输出 $q$ 行，其中第 $i$ 行表示狼想要吃掉 $x_i$ 只小猪时的攻击方案数。由于每个查询的答案可能很大，请对每个答案取模 $10^9+7$ 后输出。

In the example test, $n=2$. Thus, there are $3$ pigs at minute $1$, and $6$ pigs at minute $2$. There are three queries: $x=1$, $x=5$, and $x=6$.

If the wolf wants to eat $1$ pig, he can do so in $3+6=9$ possible attack plans, depending on whether he arrives at minute $1$ or $2$.

If the wolf wants to eat $5$ pigs, the wolf cannot arrive at minute $1$, since there aren't enough pigs at that time. Therefore, the wolf has to arrive at minute $2$, and there are $6$ possible attack plans.

If the wolf wants to eat $6$ pigs, his only plan is to arrive at the end of the convention and devour everybody.

Remember to output your answers modulo $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$ 取模后输出！