Miss Burger 最近学习了许多数据结构，其中她最喜欢的是队列。现在，她想利用两个队列来实现一种排序算法。

为此，她最初创建了两个队列 $A$ 和 $B$，它们都被初始化为空。对于一个队列，你只能进行两种操作：

• 插入（Insert）：将一个元素插入到队列的末尾。
• 弹出（Eject）：获取并移除队列头部的第一个元素。

我们将要排序的整数仅包含 $1$ 到 $n$。对于每个 $i$ ($1 \le i \le n$)，令 $a_i$ 表示数字 $i$ 的总个数。因此，总共有 $m = \sum_{i=1}^{n} a_i$ 个整数需要排序。

Miss Burger 首先将所有 $m$ 个整数重新排列成一个序列 $b$。我们称序列 $b$ 是合法的，当且仅当她能通过以下方式将所有整数按非递减顺序排序：

• 按照序列 $b$ 中整数的顺序，依次将每个整数插入到两个队列中的其中一个。
• 在所有整数插入完毕后，她开始按任意顺序逐个弹出它们。在这里，每次她可以选择从一个非空队列中弹出一个整数，并将其拼接到结果序列中。

现在，Miss Burger 想知道有多少种不同的序列 $\{b_i\}_{i=1 \dots m}$ 可以通过她的两个队列进行排序。如果两个序列 $\{b_i\}_{i=1 \dots m}$ 在某个位置 $i$ 上的值 $b_i$ 不同，则认为这两个序列是不同的。由于答案可能很大，请输出结果对 $998\,244\,353$ 取模后的值。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 500$)，表示数字的种类。 第二行包含 $n$ 个整数 $a_1, \dots, a_n$ ($0 \le a_i \le n$)，其中 $a_i$ 表示数字 $i$ 的个数。 保证 $1 \le \sum_{i=1}^{n} a_i \le 500$。

输出格式

输出一行，包含一个整数，表示合法序列的数量。 由于答案可能很大，请输出结果对 $998\,244\,353$ 取模后的值。

样例

输入 1

4
1 1 1 1

输出 1

14