考虑一个带有 $$$n$$$ 卡的游戏($$$n$$$ 是偶数)。每张卡片上都写有一个数字,介于 $$$1$$$ 和 $$$n$$$ 之间。卡上的所有数字都不同。如果 $$$x > y$$$,我们说编号为 $$$x$$$ 的牌比编号为 $$$y$$$ 的牌更强。
两名玩家,Alex 和 Boris,玩这个游戏。一开始,他们每个人都收到恰好 $$$\frac{n}{2}$$$ 卡,因此每张卡都属于一个玩家。然后,他们轮流进行。亚历克斯先走,然后鲍里斯,然后再次亚历克斯,依此类推。
在玩家的回合中,他必须恰好打出一张牌。然后,如果对手没有比所打出的牌更强的牌,则对手输,游戏结束。否则,对手必须打出一张更强的牌(也恰好是一张牌)。这两张牌从游戏中移除,回合结束。如果没有剩余牌,则游戏以平局结束;否则就轮到对手了。
考虑在两个玩家之间分配牌的所有可能方法,以便他们每个人都收到恰好一半的牌。您必须计算三个数字:
- 分配牌让 Alex 获胜的方式数量;
- 使鲍里斯获胜的分发牌的方式数量;
- 使游戏以平局结束的牌分发方式的数量。
您可以假设两个玩家都处于最佳状态(即,如果一个玩家无论对手如何玩都能赢,那么他就赢了)。如果至少有一张卡片,则两种分发卡片的方式是不同的,其中一种方式将其分发给亚历克斯,而另一种方式则将其分发给鲍里斯。
例如,假设 $$$n = 4$$$,Alex 收到卡片 $$$[2, 3]$$$,Boris 收到卡片 $$$[1, 4]$$$。那么游戏可能会这样进行:
- 如果 Alex 打出了 $$$2$$$ 牌,那么 Boris 必须用 $$$4$$$ 牌来回应。然后,亚历克斯的回合结束,鲍里斯的回合开始。鲍里斯只剩下一张牌,即$$$1$$$;他玩了它,亚历克斯用卡片 $$$3$$$ 回应。所以,比赛以平局结束;
- 如果 Alex 打出了 $$$3$$$ 牌,那么 Boris 必须用 $$$4$$$ 牌来回应。然后,亚历克斯的回合结束,鲍里斯的回合开始。鲍里斯只剩下一张牌,即$$$1$$$;他玩了它,亚历克斯用卡片 $$$2$$$ 回应。所以,比赛以平局结束。
因此,在这种情况下,游戏以平局结束。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 30$$$) — 测试用例的数量。
然后是 $$$t$$$ 行。第 $$$i$$$ 行包含一个偶数整数 $$$n$$$ ($$$2 \le n \le 60$$$)。
输出
对于每个测试用例,打印三个整数:
- 分配牌让 Alex 获胜的方式数量;
- 使鲍里斯获胜的分发牌的方式数量;
- 使游戏以平局结束的牌分发方式的数量。
由于答案可能很大,请以 $$$998244353$$$ 为模打印它们。
示例
输入 #1
5 2 4 6 8 60
输出 #1
1 0 1 3 2 1 12 7 1 42 27 1 341102826 248150916 1
注意
在第一个测试用例中,如果 Alex 收到卡片 $$$2$$$(他打出卡片,而 Boris 无法响应),则他获胜。如果 Alex 收到卡片 $$$1$$$,则游戏以平局结束。
在第二个测试用例中:
- 如果 Alex 收到纸牌 $$$[3, 4]$$$、$$$[2, 4]$$$ 或 $$$[1, 4]$$$,则他获胜;
- 如果 Alex 收到纸牌 $$$[1, 2]$$$ 或 $$$[1, 3]$$$,则鲍里斯获胜;
- 如果 Alex 收到纸牌 $$$[2, 3]$$$,则游戏以平局结束。