4307. 故障机器人

【题目背景】

不许你诋毁我第四喜欢的角色（）

【题目描述】

故障机器人有 n 个能力槽以及四种不同的能力球：电球，冰球，暗黑球和离子球。

可以将能力槽看作图上的点，能力球看作图上两个能力槽之间的有向边，那么会形成一张 n 个点的有向完全图，这张图遵循以下的连边规则：

1. 如果 a -> b 为冰球，那么 b -> a 一定为电球

2. 如果 a -> b 为电球，那么 b -> a 一定为冰球

3. 如果 a -> b 为暗黑球，那么 b -> a 一定为暗黑球

4. 如果 a -> b 为离子球，那么 b -> a 一定为离子球

我们规定一张图为有战斗力的图，当且仅当满足以下所有条件：

1. 不存在一条包含至少三个能力槽的回路，满足包含冰球，但不包含电球。

2. 不存在一条包含至少三个能力槽的回路，满足包含电球，但不包含冰球。

3. 不存在一条包含至少三个能力槽的回路，满足只包含离子球。

4. 不存在一条包含至少三个能力槽的回路，满足只包含暗黑球。

我们定义一个回路为一个点序列 $P = \{P_1, P_2, ..., P_n, P_{n + 1}\}$ 满足 

1. $P_1 = P_{n + 1}$

2. $n \ge 3$

3. $\forall i \not= j, i \not=1, j\not= n + 1, P_i \not = P_j$。

称这个序列包含边 $\forall i \le n, P_i \rightarrow P_{i + 1}$；包含点 $\forall i \le n, P_i$。

现在，故障机器人想要问你：在所有 $4^{n(n - 1) / 2}$ 种图中，一共有多少有战斗力的图，对 $998244353$ 取模。 

（注意：点有标号）

【输入格式】

第一行一个整数 q 表示 q 此询问

接下来 q 行每行一个整数 n 表示一次查询

【输出格式】

共 q 行，每行一个整数表示一次询问的答案

【样例输入】

6
1
2
3
4
5
10000000

【样例输出】

1
4
24
180
1680
214772768

【样例说明】

自己模

【数据规模与约定】

对于 60% 的数据，满足 $q = 1, n \le 5$

对于 100% 的数据，满足 $q \le 1e5, n \le 1e7$。