集合划分
将前 n 个正整数不重不漏地划分为 m 个非空集合 A1,…,Am。
一个划分是“守序”的,当且仅当存在 (1,2,…,m) 的一个环排列 (p1,…,pm),使得对每个 i 都有
maxApi>minApi−1,p0=pm.
给定正整数序列 (a1,…,am)。一个划分是“善良”的,当且仅当可以使 ∣Ai∣=ai,其中 n=∑iai。
两个划分本质不同,当且仅当存在两个数字,在一个划分中属于同一集合,而在另一个划分中属于不同集合。集合的编号不参与区分;同一集合划分只计一次,即使有多种编号方式或多种合法环排列。
求本质不同的守序善良划分数,对 998244353 取模。
输入格式
第一行一个正整数 T,表示数据组数。
每组数据两行:第一行一个正整数 m,第二行 m 个正整数 a1,…,am。
输出格式
输出 T 行,每行一个非负整数,表示对应答案。答案可以为 0。
数据范围
1≤T≤5,2≤m≤n≤100,ai≥1。
样例 1
输入
1
2
3 3
输出
9
样例解释:将六个数划分成两个大小为三的无标号集合,共有十种方案,其中只有 {1,2,3},{4,5,6} 不守序,故答案为九。