当前没有测试数据。

F - 最大直径

分数：$500$ 分

问题描述

对于一个长度为 $N$ 的由正整数组成的序列 $X=(X_1,X_2\ldots,X_N)$，我们定义 $f(X)$ 如下：

• 一棵有 $N$ 个顶点的树被称为良好树，当且仅当第 $i$ 个顶点（$1 \leq i \leq N$）的度数为 $X_i$。 如果存在一棵良好树，则 $f(X)$ 是一棵良好树的最大直径；如果不存在，则 $f(X)=0$。

这里，两个顶点之间的距离是从一个顶点到另一个顶点需要经过的最少边数， 而一棵树的直径是两个顶点之间的最大距离。

求模 $998244353$ 后，所有可能的长度为 $N$ 的正整数序列 $X$ 的 $f(X)$ 的和。 我们可以证明 $f(X)$ 的和是一个有限值。

给定 $T$ 个测试用例，求每个测试用例的答案。

约束条件

• $1\leq T \leq 2\times 10^5$
• $2 \leq N \leq 10^6$
• 输入中的所有值都是整数。

---

输入

从标准输入中以以下格式输入，其中 $\mathrm{test}_i$ 表示第 $i$ 个测试用例：

$T$

$\mathrm{test}_1$

$\mathrm{test}_2$

$\vdots$

$\mathrm{test}_T$

每个测试用例以以下格式给出：

``` $N$ ```

输出

输出 $T$ 行。

第 $i$ 行（$1\leq i \leq T$）应该包含第 $i$ 个测试用例的答案。

---

10
2
3
5
8
13
21
34
55
89
144

1
6
110
8052
9758476
421903645
377386885
881422708
120024839
351256142

如果 $N=3$，

例如，

• 当 $X=(1,1,1)$ 时，不存在三个顶点的度数依次为 $1,1$ 和 $1$ 的树，因此 $f(X)=0$。
• 当 $X=(2,1,1)$ 时，唯一可能的树如下所示。这棵树的直径为 $2$，因此 $f(X)=2$。

对于 $X=(2,1,1),(1,2,1),(1,1,2)$，我们有 $f(X)=2$；对于其他的 $X$，我们有 $f(X)=0$。因此，答案是 $6$。