Делегации трех поросят со всего мира едут на конференцию! Каждую минуту новая тройка поросят прибывает в конференц-зал. После \(n\)-й минуты конференция завершается.
Большой злой волк узнал об этой конференции и запланировал атаку. В определенную минуту конференции он ворвется в зал, съест ровно \(x\) поросят и убежит.
Волк попросил Грегора помочь ему найти количество возможных планов для атаки, в которых он съест ровно \(x\) поросят, для различных значений \(x\) (\(1 \le x \le 3n\)). Два плана для атаки считаются различными, если атака происходит в различное время, или съедаются различные подмножества поросят.
Обратите внимание, что все запросы независимы, то есть в действительности волк не ест поросят, а только строит планы!
Выходные данные
Вы должны вывести \(q\) строк. В \(i\)-й строке должно содержаться количество планов для атаки, если волк хочет съесть \(x_i\) поросят. Выведите каждый ответ по модулю \(10^9+7\).
Примечание
В приведенном примере \(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\)!
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3
1
5
6
|
9
6
1
|
|
2
|
5 4
2
4
6
8
|
225
2001
6014
6939
|