#P17960. Stonebag

Stonebag

Stonebag

有 nn 堆石子,编号为 11 到 nn,第 ii 堆最初有 aia_i 颗石子。你还有一个最初为空的袋子。

可以以任意顺序执行以下操作任意多次:

  • 选择一堆非空的石子,从中取出一颗,放进袋子。
  • 选择一堆石子(可以为空),从袋子里取出恰好 nn 颗石子,全部放入这一堆。只有袋子里至少有 nn 颗石子时才能执行此操作。

你可以随时停止操作。结束时袋子里允许留有任意数量的石子,包括非零数量。

求通过有限次操作可以得到多少种不同的石子堆最终状态,答案对 998244353998244353 取模。 如果存在某个编号的石子堆在两种状态中的石子数不同,则这两种状态不同。石子堆有标号,顺序不能忽略。

输入格式

第一行一个整数 nn(1≤n≤30001\le n\le3000)。

第二行 nn 个整数 a1,…,ana_1,\ldots,a_n(0≤ai≤1090\le a_i\le10^9)。

输出格式

输出一个整数,表示不同最终状态数对 998244353998244353 取模的结果。

样例 1

输入

2
1 3

输出

15

样例 2

输入

3
2 1 3

输出

83

样例 3

输入

8
4 3 6 5 2 0 6 3

输出

37238603