题目描述

给定 $n$ 个机器人，第 $i$ 个机器人有 $d_i$ 个接口。

你需要将机器人连接成树，方法为分别选定两个不同的机器人的一个未被选择的接口，然后连接这两个机器人。

求本质不同的树的数量，其中连接的接口不同视为树不同。

答案对 $998244353$ 取模。

输入格式

第一行一个整数 $n$。

接下来一行 $n$ 个整数 $d_i$。

输出格式

仅一行一个整数，表示本质不同的树的数量对 $998244353$ 取模的值。

样例

样例 1

3
1 1 3

6

样例 2

3
1 1 1

0

样例 3

6
7 3 5 10 6 4

389183858

样例 4

9
425656 453453 4320 1231 9582 54336 31435436 14342 423543

667877982

数据范围

对于全部数据，满足 $2\le n\le 2\times 10^5$，$1\le d_i<998244353$。