信号模拟

如下图所示，有 个仪器，中间的方块是仪器的主体，每个仪器可以充当接收器或者信号源；主体的左右两侧是两个接线点。
现在，我们将左端 个接线点随机分成 组，每组各含两个点，并将右端 个接线点同样随机分成 组。然后将每组的两个接线点用导线连接。

这样一来，我们就得到了一组封闭的信号线路。具体而言：
信号从任一信号源 出发，通过右侧接线点；
随后，信号通过与右侧接线点连接的导线到达另外一个仪器的左侧接线点，再经过仪器主体到达右侧接线点；此时，如果这个仪器是接收器，那么就视为接收到了信号（注意，接收到信号不会影响信号继续往后传递）。
这个过程持续进行，最终会形成若干个独立的循环。

现在，记 表示在所有接收器均能接收到信号的前提下， 个仪器中作为信号源的最少数量。求解 的方差。
可以证明答案可以表示为一个不可约分数 ，为了避免精度问题，请直接输出整数 作为答案，其中 ， 是满足 的整数。更具体地，你需要找到一个整数 满足 对 取模等于 ，您可以查看样例解释得到更具体的说明。
本题中，如果您需要使用到除法的取模，即计算 时， 需要使用公式 得到。例如，计算 ：

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
在一行上输入一个整数  代表仪器的数量。

对于每组测试数据，新起一行输出一个整数，表示  的方差对  取模后的结果。

3
1
2
3

0
887328314
168592380

对于第一组测试数据，左、右两侧各仅有一种配对方式，构成一个长度为 2 的循环。最小信号源数为 ，如下图所示。因此 ，。


对于第二组测试数据，左侧有三种配对（；；），右侧同样三种，合计  种等可能组合。计算可得，需要  个信号源的概率为 （如下左图所示，为其中一种情况），需要  个信号源的概率为 （如下右图所示，为其中一种情况），故：
；
。
我们能够找到，，对  取模后恰好等于分子 ，所以  是需要输出的答案。