Statement

阿菠萝又去玩游戏了，这次他想找到了若干个恐龙头套。他发现恐龙头套。

他首先会将恐龙头套按照形状，颜色，大小等分成 $n(n>1)$ 类，每一类有 $c_i(c_i>0)$ 个。然后将其排列随意排列成一个序列。而后他会将这个序列首尾相接，得到一个环。阿菠萝想要让相邻的恐龙头套尽量不同，然而事情不总是如它所愿，对于一个环，他将其分为了若干段，每段内部类型相同，相邻段类型不同。他初始的高兴值为 $1$，而后对于每一段，都会使他的高兴值除以长度的阶乘。

形式化地来说，对于每个极长的长度为 $l_i$ 的连续段，会使得高兴值 $*\frac{1}{l_i!}$。

阿菠萝现在很生气，于是他想知道对于所有排列成序列的方案他得到的高兴值之和。如果他没有得到答案，他就会将恐龙头套戴在你头上。

为了避免被带恐龙头套，请你帮帮他。

他只想知道答案对 $998244353$ 取模后的结果。

Task

input

第一行一个整数 $n$。

第二行 $n$ 个正整数 $c_1,c_2, \cdots,c_n$。

output

一行一个整数表示答案。

Sample I

input

2
2 2

output

3

Hint

一共 $6$ 种序列：

{1,1,2,2}(1/4),{1,2,2,1}(1/4),{1,2,1,2}(1),
{2,1,2,1}(1),{2,2,1,1}(1/4),{2,1,1,2}(1/4)

Sample II

input

6
7 8 9 10 11 12

output

526836707

Constraints

对于 $100\%$ 的数据，$1<n\le 200000, \sum c_i\le 200000, c_i\ge 1$

$\textbf{subtask 1(15 pts)}$：$\sum c_i\le 10$

$\textbf{subtask 2(15 pts)}$：$n\le 100,c_i\le 100$

$\textbf{subtask 3(20 pts)}$：$n\le 500,c_i\le 500$

$\textbf{subtask 4(20 pts)}$：$n=2$

$\textbf{subtask 5(30 pts)}$：无特殊限制