P17540 发迹

:::epigraph[——《发迹》] 我种的种子从来没结果 我把自己关在家里 想要给自己点空间 ::: 

定义一个包含 $k$ 种类型元素的序列 $a$（下标从 $1$ 开始）的一个重排的权值为其最长的满足如下条件的子区间 $[L,R]$ 的长度： - $L\ne 1$。 - $\forall i\in[0,R-L],a_{i+1}=a_{i+L}$。 特别地，如果没有满足条件的子区间，则重排的权值为 $0$。 Barry 有一个长度为 $n$ 的序列 $a$，求序列 $a$ 的所有重排中，权值最小的重排数量对 $998244353$ 取模的值。两个重排不同，当且仅当存在一个位置上两个重排中元素的类型不同。 显然，序列初始的元素顺序对答案没有影响。所以为了减小输入量，我们将给你一个长度为 $k$ 的序列 $c$，$c_i$ 表示序列中 $i$ 类型元素出现的次数，而上述问题中的 $n=\sum\limits_{i=1}^kc_i$。

**本题包含多组测试。** 第一行一个整数 $T$，表示测试数据组数。对于每组测试数据： 第一行一个整数 $k$，意义如题目所示。 接下来 $k$ 个用空格隔开的整数，表示出现次数序列 $c_i$。

输出 $T$ 行，每行一个整数，表示对应测试数据的答案。

### 数据范围 **本题开启捆绑测试。** 对于 $100\%$ 的测试数据，$1\le T\le 5$，$1\le k\le 2\times 10^5$，$1\le c_i\le 10^7$，$1\le n\le 10^7$。 | 子任务 | $k\le$ | $n\le$ | 得分 | |:-:|:-:|:-:|:-:| | 1 | $8$ | $8$ | $12$ | | 2 | $300$ | $300$ | $12$| | 3 | $3000$ | $3000$ | $16$ | | 4 | $2$ | $10^7$ | $8$ | | 5 | $3000$ | $10^7$ | $20$ | | 6 | $2\times 10^5$ | $2\times 10^5$ | $12$ | | 7 | $2\times 10^5$ | $10^7$ | $20$ | ### 后记 :::epigraph[——《发迹》] 真的 有数不清的遗憾 但现在看来觉得没什么 那天我流了很多泪 在那之后我告诉自己就不再轻易 cry :::