На этот раз Ехаб будет играть с перестановками. У него есть \(n\) кубиков, расположенных в ряд, с числами от \(1\) до \(n\), написанными на них. Он сделает ровно \(j\) операций. В ходе каждой из операций он выбирает \(2\) кубика и меняет их местами.
Ехаб задался вопросом: сколько различных последовательностей кубиков я могу получить в конце? Так как Ехаб непостоянный человек, он не уверен, сколько операций хочет совершить. Поэтому он просит вас узнать ответ на его вопрос для всех \(j\) от \(1\) до \(k\).
Выходные данные
Выведите \(k\) целых чисел. \(i\)-е из них — это количество возможных последовательностей, которые можно получить после ровно \(i\) операций. Так как это число может быть очень большим, выведите его остаток от деления на \(10^9+7\).
Примечание
Во втором примере есть \(3\) последовательности, которые можно получить после \(1\) операции, потому что вы можете поменять местами \(3\) различные пары индексов. Также, есть ровно \(3\) последовательности, которые можно получить после \(2\) операций:
- \([1,2,3]\),
- \([3,1,2]\),
- \([2,3,1]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3
|
1 1 1
|
|
2
|
3 2
|
3 3
|
|
3
|
4 2
|
6 12
|