The Three Little Pigs

题意翻译

+ 有一个最初为空箱子，一共有 $n$ 天，每天开始时箱子里会多出 $3$ 个球，**所有球互不相同**。 + 有一个参数 $x$。我们认为一次行动为在某天**球数增加后**从箱子里选出 $x$ 个球拿走。注意如果箱子里的球数少于 $x$，那么当天无法进行行动。 + 给定 $n$ 和 $q$，有 $q$ 次询问，每次询问给定 $x$，你需要求出有多少种行动方案，对 $10^9+7$ 取模。注意对于一次行动方案，你**只能执行最多一次且必须执行一次行动**。 + 两种行动不同当且仅当进行行动的天数不同，或者拿走的球的集合不同。 + 注意行动并没有真正执行，只需要计算出方案数。

题目描述

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!

输入输出格式

输入格式

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.

输出格式

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 $ .

输入输出样例

输入样例 #1

2 3
1
5
6

输出样例 #1

9
6
1

输入样例 #2

5 4
2
4
6
8

输出样例 #2

225
2001
6014
6939

说明

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