题面

时间限制：4s

空间限制：1024MB

题目描述

对于一个图 $(V,E)$，设 $|V|=n$，称它为剖分图，当且仅当它满足如下条件：

1. 它是一个简单无向无权图。
2. $\forall i\in[1,n-1]\cap\mathbb N$，边 $(i,i+1)$ 存在，并且边 $(1,n)$ 存在。
3. $\forall u,v,w,s\in[1,n]\cap\mathbb N$，若 $u<w<v<s$，则边 $(u,w)$ 和 $(v,s)$ 不同时存在。

对于一个图 $(V,E)$，称它为三角剖分图,当且仅当它满足如下条件：

1. 它是一个剖分图。
2. $\forall E'\supsetneq E$，$(V,E')$ 不是一个剖分图。

对于一个三角剖分图 $(V,E)$，定义其权值为：

$$\sum\limits_{u=1}^n\sum\limits_{v=u+1}^n\sum\limits_{w=1}^n\sum\limits_{s=w+1}^n[(u,v)\in E]([u<w<v<s]+[w<u<s<v]) $$

现给定 $n$，你需要回答以下两个问题：

• 第一问：存在多少个点数为 $n$ 的三角剖分图有欧拉回路。
• 第二问：所有点数为 $n$ 的有欧拉回路的三角剖分图的权值和为多少。

这里规定点集均为 $V=[1,n]\cap\mathbb N$，两个图 $(V,E)$ 和 $(V,E')$ 不同当且仅当 $E\neq E'$。

由于答案太大，你只需要输出答案在模 $998244353$ 下的结果即可。

输入格式

从文件 $\textit{\textbf{discrete.in}}$ 中读入数据。

本题有多组测试数据。

输入的第一行包含一个正整数 $T$，表示数据组数。

接下来包含 $T$ 组数据，每组数据包含一行一个整数 $n$。

输出格式

输出到文件 $\textit{\textbf{discrete.out}}$ 中。

对于每组测试数据输出一行包含两个用单个空格隔开的整数，分别表示第一问和第二问的答案。

样例 1 输入

10
3
5
6
7
9
39
456
18546
314151
2147481

样例 1 输出

1 0
0 0
2 18
0 0
9 432
863008632 948323789
610014751 183318344
377974316 250221019
440758819 84245235
870622289 556821837

评分方式

每个测试点 $5$ 分。

每一行应按顺序输出两问的答案，不符合输出格式的输出得 $0$ 分。

程序仅回答对第一问得 $4$ 分，仅回答对第二问得 $1$ 分，两问都答对得 $5$ 分。

如果你不回答第一问或第二问，也需要在对应位置上输出一个整数以满足输出格式。

建议用 $0$ 占位，不保证使用其他数占位会使你得到应得的分数。

数据范围

对于所有数据，保证 $T\in[1,10^5]\cap\mathbb N,n\in[3,3\times10^6]\cap\mathbb N$。

测试点编号	$n$
$1\sim4$	$15$
$5\sim6$	$300$
$7\sim11$	$8\times10^3$
$12\sim14$	$5\times10^4$
$15\sim18$	$4\times10^5$
$19\sim20$	$3\times10^6$

注意所有数据对 $T$ 的限制相同。

样例下载：discrete