C. Три поросенка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Делегации трех поросят со всего мира едут на конференцию! Каждую минуту новая тройка поросят прибывает в конференц-зал. После $$$n$$$-й минуты конференция завершается.

Большой злой волк узнал об этой конференции и запланировал атаку. В определенную минуту конференции он ворвется в зал, съест ровно $$$x$$$ поросят и убежит.

Волк попросил Грегора помочь ему найти количество возможных планов для атаки, в которых он съест ровно $$$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$$$.

Примеры
Входные данные
2 3
1
5
6
Выходные данные
9
6
1
Входные данные
5 4
2
4
6
8
Выходные данные
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$$$!