E. Парные скобочные последовательности
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Фермер Джон интересуется скобочными последовательностями с общими парами.

Правильной скобочной последовательностью называется последовательность, в которой каждой открывающей скобке сопоставлена более поздняя закрывающая скобка, а ни в одном префиксе закрывающих скобок не больше, чем открывающих.

Для правильной скобочной последовательности $$$s$$$ правильной называется пара позиций $$$(i,j)$$$, где $$$i \lt j$$$, такая, что $$$s_i$$$ — открывающая скобка, $$$s_j$$$ — закрывающая скобка, а подстрока строго между ними является правильной скобочной последовательностью.

Рассмотрим упорядоченную пару $$$(s,t)$$$ правильных скобочных последовательностей, где обе последовательности $$$s$$$ и $$$t$$$ имеют длину $$$2n$$$. Правильная пара $$$(i,j)$$$ является общей для $$$s$$$ и $$$t$$$, если $$$(i,j)$$$ является правильной парой в обеих последовательностях. Например, у скобочных последовательностей $$$\texttt{(()())}$$$ и $$$\texttt{((()))}$$$ есть одна общая правильная пара — внешняя пара $$$(1,6)$$$.

Две упорядоченные пары $$$(s,t)$$$ и $$$(s',t')$$$ считаются различными, если $$$s \ne s'$$$ или $$$t \ne t'$$$.

Для каждого $$$0 \le k \le n$$$ Фермер Джон хочет узнать количество упорядоченных пар $$$(s,t)$$$ правильных скобочных последовательностей длины $$$2n$$$ с ровно $$$k$$$ общими правильными парами. Поскольку эти количества могут быть большими, выведите их по модулю $$$M$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных содержатся два целых числа $$$n$$$ и $$$M$$$ ($$$1 \leq n \leq 500$$$, $$$10^8 \leq M \leq 10^9$$$) — половина длины скобочной последовательности и модуль, по которому нужно вывести ответ. Гарантируется, что $$$M$$$ является простым.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$500$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n + 1$$$ целых чисел — ответ по модулю $$$M$$$ для каждого $$$0 \leq k \leq n$$$.

Пример
Входные данные
5
1 998244353
2 998244353
3 998244353
4 998244353
8 998244353
Выходные данные
0 1 
2 0 2 
8 12 0 5 
62 64 56 0 14 
378790 646560 542960 296800 127400 34944 16016 0 1430
Примечание

В первом наборе входных данных существует только одна правильная скобочная последовательность для $$$n=1$$$: $$$\texttt{()}$$$. У неё есть ровно одна правильная пара, а именно $$$(1,2)$$$. Поэтому единственная упорядоченная пара скобочных последовательностей имеет ровно одну общую правильную пару, и ответ равен $$$[0,1]$$$.

Во втором наборе входных данных существуют ровно две правильные скобочные последовательности для $$$n=2$$$: $$$a=\texttt{(())}$$$ и $$$b=\texttt{()()}$$$. Правильные пары последовательности $$$a$$$ — это $$$(1,4)$$$ и $$$(2,3)$$$, а правильные пары последовательности $$$b$$$ — это $$$(1,2)$$$ и $$$(3,4)$$$.

Таким образом, упорядоченные пары $$$(a,b)$$$ и $$$(b,a)$$$ имеют $$$0$$$ общих правильных пар, а упорядоченные пары $$$(a,a)$$$ и $$$(b,b)$$$ имеют $$$2$$$ общие правильные пары. Поэтому ответ равен $$$[2,0,2]$$$.