期中考试考完了，已经感到没有什么好害怕的六花今天决定不学数学了，于是和勇太打起了游戏王。

“你已空手空场，生命只剩一百，事到如今你还能做什么？”

“所累哇多卡纳！”

“纳尼？”

然而六花的卡组实在是太菜了，经过分析，六花发现在一回合内，她卡组中的牌并没有办法达成 OTK，除非主角光环附体：

被封印的艾克佐迪亚

——包括这张卡在内，「被封印者的右足」「被封印者的左足」「被封印者的右腕」「被封印者的左腕」全在手牌的时候，获得决斗胜利。

但是因为六花不是高贵的氪金玩家，她可以肯定，这五张牌中肯定有一张，在牌堆的底端。所以六花现在面临着一个难题：需要在一回合内将卡组抽完。

六花的牌堆一共有 $m+1$ 张牌，因为最后一张牌是固定的，所以我们现在只考虑前 $m$ 张牌。

在这 $m$ 张牌中，有 $n$ 张特殊牌和 $m-n$ 张普通牌，每一个特殊牌有一个属性值 $w_i$，表示在打出这张牌后，可以再摸 $w_i$ 张牌。幸运的是，六花发现这些牌刚好满足 $\sum_{i=1}^n w_i=m$，因此她可以放心的随意摸牌而不用担心爆牌。

因为这 $m$ 张牌是被打乱的，所以总共有 $m!$ 种不同的可能的牌堆。

现在这回合开始了，六花先从牌堆里抽出一张牌，接着六花不断的打出手中的牌，如果打出特殊牌，则又可以摸牌，直到摸到最后一张牌达成胜利条件或者打光自己的手牌结束自己的回合继而输掉比赛。

举例来说，如果牌堆是 $\{4,0,0,2,0,0,0\}$（用 $0$ 表示普通牌，其他数字表示 $w_i$，其中最后一个 $0$ 是最后一个部件），那么六花打牌的过程可以为：

1. 取一张牌，手中的牌为 $\{4\}$。
2. 打出 $\{4\}$，再取四张牌，手中的牌为 $\{0,0,2,0\}$。
3. 打出 $\{2\}$，还需要再取两张，这时已摸到最后一个部件，六花胜利。

而如果牌堆是 $\{2,0,0,4,0,0,0\}$，不难发现是勇太的胜利。

现在，六花想要知道这 $m!$ 种不同的牌堆中，有多少种能够让她胜利。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个空格隔开的正整数 $w_i$。

通过输入你可以自己算出来 $m=\sum_{i=1}^n w_i$

输出格式

输出一个整数表示答案，答案可能很大，你只需要输出对 $998244353$ 取模后的结果。

样例一

input

1
5

output

24

explaination

所有可能的 $m!$ 种牌堆中，只有形如 $\{5,0,0,0,0,0\}$ 的 $24$ 个牌堆满足条件。

样例二

input

6
1 2 3 4 5 6

output

90337303

样例三

见样例数据下载

样例四

见样例数据下载

限制与约定

对于 $10\%$ 的数据，$m \leq 10$。

对于 $30\%$ 的数据，$n \leq 8$。

对于 $50\%$ 的数据，$n \leq 15$。

对于 $70\%$ 的数据，$n \leq 30$。

对于 $100\%$ 的数据，$n \leq 40$，$1 \leq w_i \leq 10^5$

同时保证有 $m-n \geq 4$，因为牌堆里毕竟要有这 $5$ 个部件嘛。

时间限制：$2\texttt{s}$

空间限制：$256\texttt{MB}$

下载

样例数据下载