给定 $n$ 堆石头，用 $1$ 到 $n$ 的整数标号。第 $i$ 堆最初包含 $a_i$ 块石头。

你还有一个袋子，最初是空的。

你可以以任意顺序执行以下操作任意次：

• 选择一个非空的堆，从该堆中取出一块石头，并将其放入袋子中。
• 选择一个堆（可能为空），从袋子中取出恰好 $n$ 块石头，并将这 $n$ 块石头全部放入所选的堆中。只有当袋子中至少有 $n$ 块石头时，才能执行此操作。

你可以随时停止执行操作。最后，袋子中可以包含任意（可能非零）数量的石头。

求通过执行有限次操作，可以从初始状态得到多少种不同的 $n$ 堆石头的最终状态。输出答案对 $998244353$ 取模的结果。

如果存在某个索引 $i$，使得两者的第 $i$ 堆石头数量不同，则认为两种最终状态是不同的。请注意，这些堆是有标号的，它们的顺序很重要。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 3000$)，表示石头的堆数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$)，其中 $a_i$ 是第 $i$ 堆最初的石头数量。

输出格式

输出一个整数：可以得到的不同的石头堆最终状态的数量，对 $998244353$ 取模。

样例

输入样例 1

2
1 3

输出样例 1

15

输入样例 2

3
2 1 3

输出样例 2

83

输入样例 3

8
4 3 6 5 2 0 6 3

输出样例 3

37238603