#P18455. Queue Sorting

Queue Sorting

Queue Sorting

题目描述

Burger 最近学习了许多数据结构,她最喜欢的是队列。她想用两个队列实现排序算法。

初始时,队列 AA 和 BB 都为空。对于一个队列,只能进行下列操作:

  • 插入:把一个元素放到队尾。
  • 弹出:取得并删除队首元素。

需要排序的整数只包含 11 到 nn。对于每个 ii,整数 ii 总共有 aia_i 个。记这些整数的总数为

m=∑i=1nai.m=\sum_{i=1}^{n}a_i.

Burger 可以把这 mm 个整数任意排列为一个序列 bb。当且仅当她能按照以下过程,将所有整数按非降顺序取出时,称 bb 合法:

  1. 按 bb 中的顺序依次处理每个整数,把它插入两个队列中的任意一个。
  2. 所有整数都插入完毕后,才开始依次弹出整数。每次可以选择任意一个非空队列,弹出其队首,并将该整数接到结果序列的末尾。最终结果须为非降序列。

她想知道有多少个不同的序列 bb 是合法的。两个序列不同,当且仅当至少存在一个位置,其数值不同;同一个值的不同副本不作区分,同一序列的不同入队方案也不重复计数。

答案可能很大,请对 998244353998244353 取模。

输入格式

第一行包含一个整数 nn,满足 1≤n≤5001\le n\le500,表示整数的种类范围。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,满足 0≤ai≤n0\le a_i\le n。保证

1≤∑i=1nai≤500.1\le\sum_{i=1}^{n}a_i\le500.

输入只有上述一个实例,没有外层测试数据组数。允许某些数值出现 00 次,但总数至少为 11。

输出格式

输出一行一个整数,表示合法序列数量对 998244353998244353 取模的结果。

原样例

4
1 1 1 1
14