You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

来源：2019 集训队作业 Round4

题目描述

若干个正整数排成一个序列，其中数字 $i$ 的出现次数为 $c_i$，对于每一个这样的序列，定义他的权值如下：

把这个序列首尾相接放在一个圆上，把这些数字分成若干相邻的段，使得每段都是在圆上相邻的数字，任意两段没有公共的元素，每一段中的数字都相同，相邻段中的数字不同，则这个序列的权值定义为所有段的长度之积。

求所有的序列的权值和对 $998244353$ 取模。

注：虽然计算序列的权值的时候是圆排列，但互为循环排列的不同序列仍然被认为是不同的，如 $(1,2,1,2)$ 和 $(2,1,2,1)$ 被认为是不同的序列。

输入格式

若干行，第一行一个正整数 $n$ ，表示数字种类数。

第二行 $n$ 个正整数 $c_i$，表示第 $i$ 个数字的出现次数。

输出格式

一行，表示所有出现次数符合条件的序列的权值和对 $998244353$ 取模的值。

2
2 2

18

6
7 8 9 10 11 12

515320459

提示

样例解释 #1：

合法序列为 $(1,1,2,2),(1,2,1,2),(1,2,2,1),(2,1,1,2),(2,1,2,1),(2,2,1,1)$。 权值分别为 $4,1,4,4,1,4$，和为 $18$。

$\sum c_i \le 2\times 10^5$

$2\le n\le 2\times 10^5$