三角染色

题目描述

Y 同学正在研究一种特殊的图论结构。给定一个包含 $N$ 个顶点和 $N$ 条边的无向图，其中 $N$ 是 $6$ 的倍数。每条边都有一个正整数权值。

这个图的结构非常规则，它由 $\frac{N}{3}$ 个独立的“三元组”组成。具体来说，第 $i$ 个三元组（$1 \le i \le \frac{N}{3}$）包含顶点 $3i-2$、$3i-1$ 和 $3i$。在每个三元组内部，三个顶点两两之间都有一条边相连（即构成一个三角形 $K_3$），而不同三元组的顶点之间不存在任何边。

Y 同学需要对图中的每个顶点进行染色，颜色只能是红色或蓝色。染色必须满足以下两个条件：

1. 每个顶点必须恰好染一种颜色。
2. 图中红色顶点的总数必须等于蓝色顶点的总数，即两种颜色的顶点数均为 $\frac{N}{2}$。

如果一个染色方案满足上述条件，则称其为合法方案。

对于一个合法方案，Y 同学定义其权值为：所有连接不同颜色顶点的边的权值之和。

Y 同学希望找到所有合法方案中权值的最大值，记为 $W$。请你帮助他计算，一共有多少种合法染色方案的权值恰好等于 $W$。

由于答案可能非常大，请输出答案对 $998244353$ 取模后的结果。

输入格式

第一行包含一个整数 $N$，满足 $6 \le N \le 3 \times 10^5$ 且 $N \equiv 0 \pmod 6$。

第二行包含 $N$ 个整数 $w_1, w_2, \dots, w_N$（$1 \le w_i \le 1000$），表示边的权值。 边的输入顺序如下：

• 对于第 $1$ 个三元组（顶点 $1, 2, 3$）：$w_1$ 连接 $(1, 2)$，$w_2$ 连接 $(1, 3)$，$w_3$ 连接 $(2, 3)$。
• 对于第 $2$ 个三元组（顶点 $4, 5, 6$）：$w_4$ 连接 $(4, 5)$，$w_5$ 连接 $(4, 6)$，$w_6$ 连接 $(5, 6)$。
• 以此类推，对于第 $k$ 个三元组，接下来的三个权重分别对应边 $(3k-2, 3k-1)$、$(3k-2, 3k)$ 和 $(3k-1, 3k)$。

输出格式

输出一行一个整数，表示权值等于最大值 $W$ 的合法染色方案的数量，结果对 $998244353$ 取模。

样例

样例输入 #1

12
1 3 3 7 8 5 2 2 2 2 4 2

样例输出 #1

36

样例输入 #2

6
4 2 6 6 6 4

样例输出 #2

2

数据范围与约定

对于 $100\%$ 的数据，保证 $6 \le N \le 3 \times 10^5$，$N \% 6 == 0$，$1 \le w_i \le 1000$。