CF1795D.Triangle Coloring

You are given an undirected graph consisting of $n$ vertices and $n$ edges, where $n$ is divisible by $6$. Each edge has a weight, which is a positive (greater than zero) integer.

The graph has the following structure: it is split into $\frac{n}{3}$ triples of vertices, the first triple consisting of vertices $1, 2, 3$, the second triple consisting of vertices $4, 5, 6$, and so on. Every pair of vertices from the same triple is connected by an edge. There are no edges between vertices from different triples.

You have to paint the vertices of this graph into two colors, red and blue. Each vertex should have exactly one color, there should be exactly $\frac{n}{2}$ red vertices and $\frac{n}{2}$ blue vertices. The coloring is called valid if it meets these constraints.

The weight of the coloring is the sum of weights of edges connecting two vertices with different colors.

Let $W$ be the maximum possible weight of a valid coloring. Calculate the number of valid colorings with weight $W$, and print it modulo $998244353$.

你被给定一个包含 $n$ 个顶点和 $n$ 条边的无向图，其中 $n$ 可被 $6$ 整除。每条边都有一个权值，该权值为正整数（即大于零）。

该图具有如下结构：它被划分为 $\frac{n}{3}$ 个三元组顶点，第一个三元组包含顶点 $1, 2, 3$，第二个三元组包含顶点 $4, 5, 6$，依此类推。同一三元组内的任意两个顶点之间均有一条边相连；不同三元组之间的顶点不存在边。

你需要将该图的所有顶点染成两种颜色：红色与蓝色。每个顶点必须恰好染一种颜色，且红色顶点与蓝色顶点的数量都必须恰好为 $\frac{n}{2}$。满足上述约束的染色方案称为合法染色。

染色方案的权值定义为：所有连接两个不同颜色顶点的边的权值之和。

令 $W$ 表示所有合法染色方案中可能达到的最大权值。请计算权值恰好为 $W$ 的合法染色方案总数，并将结果对 $998244353$ 取模后输出。

The first line contains one integer $n$ ($6 \le n \le 3 \cdot 10^5$, $n$ is divisible by $6$).

The second line contains $n$ integers $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 1000$) — the weights of the edges. Edge $1$ connects vertices $1$ and $2$, edge $2$ connects vertices $1$ and $3$, edge $3$ connects vertices $2$ and $3$, edge $4$ connects vertices $4$ and $5$, edge $5$ connects vertices $4$ and $6$, edge $6$ connects vertices $5$ and $6$, and so on.

第一行包含一个整数 $n$（$6 \le n \le 3 \cdot 10^5$，且 $n$ 能被 $6$ 整除）。

第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$（$1 \le w_i \le 1000$），表示各条边的权重。其中，第 $1$ 条边连接顶点 $1$ 和 $2$，第 $2$ 条边连接顶点 $1$ 和 $3$，第 $3$ 条边连接顶点 $2$ 和 $3$，第 $4$ 条边连接顶点 $4$ 和 $5$，第 $5$ 条边连接顶点 $4$ 和 $6$，第 $6$ 条边连接顶点 $5$ 和 $6$，依此类推。

Print one integer — the number of valid colorings with maximum possible weight, taken modulo $998244353$.

输出一个整数——具有最大可能权重的有效染色方案的数量，对 $998244353$ 取模。

The following picture describes the graph from the first example test.

The maximum possible weight of a valid coloring of this graph is $31$.

下图描述了第一个示例测试用例中的图。

该图的有效着色的最大可能权重为 $31$。