#P18746. [正睿NOI2021训练] 集合划分

[正睿NOI2021训练] 集合划分

集合划分

将前 nn 个正整数不重不漏地划分为 mm 个非空集合 A1,…,AmA_1,\ldots,A_m。

一个划分是“守序”的,当且仅当存在 (1,2,…,m)(1,2,\ldots,m) 的一个环排列 (p1,…,pm)(p_1,\ldots,p_m),使得对每个 ii 都有

max⁡Api>min⁡Api−1,p0=pm.\max A_{p_i}>\min A_{p_{i-1}},\qquad p_0=p_m.

给定正整数序列 (a1,…,am)(a_1,\ldots,a_m)。一个划分是“善良”的,当且仅当可以使 ∣Ai∣=ai|A_i|=a_i,其中 n=∑iain=\sum_i a_i。

两个划分本质不同,当且仅当存在两个数字,在一个划分中属于同一集合,而在另一个划分中属于不同集合。集合的编号不参与区分;同一集合划分只计一次,即使有多种编号方式或多种合法环排列。

求本质不同的守序善良划分数,对 998244353998244353 取模。

输入格式

第一行一个正整数 TT,表示数据组数。

每组数据两行:第一行一个正整数 mm,第二行 mm 个正整数 a1,…,ama_1,\ldots,a_m。

输出格式

输出 TT 行,每行一个非负整数,表示对应答案。答案可以为 00。

数据范围

1≤T≤51\le T\le5,2≤m≤n≤1002\le m\le n\le100,ai≥1a_i\ge1。

样例 1

输入

1
2
3 3

输出

9

样例解释:将六个数划分成两个大小为三的无标号集合,共有十种方案,其中只有 {1,2,3},{4,5,6}\{1,2,3\},\{4,5,6\} 不守序,故答案为九。