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

Рассмотрим игру с $$$n$$$ картами ($$$n$$$ четное). На каждой карте написано число от $$$1$$$ до $$$n$$$. Числа на всех картах различны. Скажем, что карта с числом $$$x$$$ сильнее карты с числом $$$y$$$, если $$$x > y$$$.

Два игрока, Алексей и Борис играют в эту игру. В начале каждый из них получает ровно по $$$\frac{n}{2}$$$ карт, так что каждая карта находится ровно у одного игрока. Затем они ходят по очереди. Сначала ходит Алексей, затем Борис, затем снова Алексей и так далее.

На своем ходу игрок должен сыграть ровно одну из своих карт. Затем, если у соперника нет карт сильнее сыгранной карты, то соперник проигрывает, и игра заканчивается. Иначе соперник должен сыграть карту сильнее сыгранной (тоже ровно одну). Эти две карты удаляются из игры, и ход заканчивается. Если карт больше нет, то игра заканчивается вничью; иначе ход переходит к сопернику.

Рассмотрим все способы распределить карты между двумя игроками так, чтобы у каждого была ровно половина всех карт. Вам надо посчитать три величины:

  • количество способов раздать карты так, чтобы выиграл Алексей;
  • количество способов раздать карты так, чтобы выиграл Борис;
  • количество способов раздать карты так, чтобы игра закончилась вничью.

Полагаем, что оба игрока играют оптимально (т. е. если игрок может выиграть вне зависимости от действий его соперника, то он выигрывает). Два способа раздать карты считаются различными, если есть хотя бы одна такая карта, что в одном из способов она у Алексея, а в другом — у Бориса.

Например, пусть $$$n = 4$$$, Алексей получает карты $$$[2, 3]$$$, а Борис получает карты $$$[1, 4]$$$. Игра может пойти следующим образом:

  • если Алексей играет карту $$$2$$$, Борис должен ответить картой $$$4$$$. Ход Алексея заканчивается, и начинается ход Бориса. У Бориса осталась только карта $$$1$$$; он играет ее, и Алексей отвечает картой $$$3$$$. Игра заканчивается ничьей;
  • если Алексей играет карту $$$3$$$, Борис должен ответить картой $$$4$$$. Ход Алексея заканчивается, и начинается ход Бориса. У Бориса осталась только карта $$$1$$$; он играет ее, и Алексей отвечает картой $$$2$$$. Игра заканчивается ничьей.

Таким образом, в этом случае игра заканчивается вничью.

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

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 30$$$) — количество наборов входных данных.

Затем следуют $$$t$$$ строк. В $$$i$$$-й строке записано одно четное число $$$n$$$ ($$$2 \le n \le 60$$$).

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

На каждый набор входных данных выведите три числа:

  • количество способов раздать карты так, чтобы выиграл Алексей;
  • количество способов раздать карты так, чтобы выиграл Борис;
  • количество способов раздать карты так, чтобы игра закончилась вничью.

Так как ответ может быть достаточно большим, выведите его по модулю $$$998244353$$$.

Пример
Входные данные
5
2
4
6
8
60
Выходные данные
1 0 1
3 2 1
12 7 1
42 27 1
341102826 248150916 1
Примечание

В первом наборе входных данных Алексей выигрывает, если он получает карту $$$2$$$ (он ее играет, а Борис не может ответить). Если Алексей получает карту $$$1$$$, то игра заканчивается вничью.

Во втором наборе входных данных:

  • Алексей выигрывает, если он получает карты $$$[3, 4]$$$, $$$[2, 4]$$$ или $$$[1, 4]$$$;
  • Борис выигрывает, если Алексей получает карты $$$[1, 2]$$$ или $$$[1, 3]$$$;
  • игра заканчивается вничью, если Алексей получает карты $$$[2, 3]$$$.