The Three Little Pigs
Contest: Codeforces Round 736 (Div. 1)
Difficulty rating: 2500
Tags: combinatorics, dp, fft, math

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!

Input format:
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.

Output format:
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$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 512.0 MB

Note:
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$$$!

Example input:
2 3
1
5
6

Example output:
9
6
1

Example input:
5 4
2
4
6
8

Example output:
225
2001
6014
6939

Editorial:
For a given $$$x$$$, we want to compute $$$\sum_{i=1}^{N}{\binom{3i}{x}}$$$, which can be solved with a combinatorial dynamic programming.
Define the array $$$dp[x][m]$$$ (dimensions: $$$N+1\times 3$$$), which computes the sum $$$\sum_{i=0}^{N-1}{\binom{3i+m}{x}}$$$. Under this definition, $$$ans[x]=dp[x][0]+\binom{3N}{x}$$$, where $$$ans$$$ is what we want to find.
Under the definition of the dp, we can make the following mathematical observations.
$$$dp[x][0]+dp[x][1]+dp[x][2]=\sum_{i=0}^{3N-1}{\binom{i}{x}}$$$, since term $$$i$$$ belongs to the array with $$$m=i\mod{3}$$$. This summation can be condensed with the Hockey Stick Identity into $$$\binom{3N}{x+1}$$$.
By repeated uses of Pascal's Identity, we get equations (2) and (3), giving us a system of 3 equations with 3 new unknowns, which can easily be solved.
1. $$$\sum_{m=0}^{2}{dp[x][m]}=\binom{3N}{x+1}$$$.
2. $$$dp[x][1] = dp[x][0]+dp[x-1][0]$$$
3. $$$dp[x][2] = dp[x][1]+dp[x-1][1]$$$
The base case is that $$$dp[0][0]=dp[0][1]=dp[0][2]=N$$$. Each query can now be answered trivially.
The time complexity is $$$\mathcal{O}(N)$$$ with combinatorial precomputation.
ALTERNATE SOLUTION WITH POLYNOMIAL LONG DIVISION:
Define the polynomial $$$P(k)=(1+k)^3+(1+k)^6+\cdot + (1+k)^{3N}$$$.
The coefficient of $$$k^x$$$ in $$$P(k)$$$ is, by the Binomial theorem on each term of the polynomial, equal to $$$\binom{3}{x}+\binom{6}{x}+\cdot + \binom{3N}{x}$$$. This is equal to $$$ans[x]$$$ from the previous solution.
The only thing left to do is quickly calculate $$$P(k)$$$. Due to the tight time limit, calculating the polynomial using FFT in $$$\mathcal{O}{(N\log{N})}$$$ is probably too slow.
Instead, we notice that $$$P(k)$$$ is a geometric series. Using the geometric series formula, we get that $$$P(k)=\frac{(1+k)^{3N+3}-(1+k)^3}{(1+k)^3-1}$$$.
The numerator and denominator of this fraction can be expanded in linear time. Then all we have to do is a polynomial long division. Once we have $$$P(k)$$$, we can answer all the queries trivially.
The time complexity is $$$\mathcal{O}(N)$$$ with combinatorial precomputation.