该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

现有 $N$ 种颜色的旗子，每种颜色的旗子都有一定数量（对于相同颜色的旗子，可以认为是完全相同的）。

先将这 $N$ 种颜色的所有彩旗组成一排彩旗，问一共有多少种方案？

因为答案会很大，请将答案模 $998 \ 244 \ 353$ 输出。

Format

Input

第一行包含 $1$ 个正整数 $N$，表示旗子颜色种类数。

接下来一行包含 $N$ 个整数，$a_i$ 表示第 $i$ 种颜色旗子的数量为 $a_i$。

$1 \le N \le 10^3, 1 \le a_i \le 10^3$ 。

Output

一个整数，表示组成一排彩旗的方案数。

Samples

4
4 3 2 5

2522520