给定一个由 $$$n$$$ 顶点和 $$$n$$$ 边组成的无向图,其中 $$$n$$$ 可被 $$$6$$$ 整除。每条边都有一个权重,它是一个正(大于零)整数。
该图具有以下结构:它被分成 $$$\frac{n}{3}$$$ 个顶点三元组,第一个三元组由顶点 $$$1, 2, 3$$$ 组成,第二个三元组由顶点 $$$4, 5, 6$$$ 组成,依此类推。同一三元组中的每对顶点都通过一条边连接。不同三元组的顶点之间没有边。
您必须将此图的顶点绘制为两种颜色:红色和蓝色。每个顶点应该只有一种颜色,应该有 $$$\frac{n}{2}$$$ 红色顶点和 $$$\frac{n}{2}$$$ 蓝色顶点。如果满足这些约束,则着色被称为有效。
着色的权重是连接两个不同颜色的顶点的边的权重之和。
设 $$$W$$$ 为有效着色的最大可能重量。计算权重 $$$W$$$ 的有效着色数量,并以 $$$998244353$$$ 为模打印。
输入
第一行包含一个整数 $$$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$$$,依此类推。
输出
打印一个整数 — 具有最大可能重量的有效着色数量,以 $$$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
注意
下图描述了第一个示例测试的图表。
该图有效着色的最大可能权重为 $$$31$$$。