SP4202 BRPAR - Brackets Parade

给定若干组括号，计算由这些括号组成的不同的正确括号序列的数量。假设有 $k_1$ 对第 1 类括号、$k_2$ 对第 2 类括号、……、$k_m$ 对第 $m$ 类括号。一个括号序列被称为正确的，当且仅当符合以下任一条件： - 空序列是正确的； - 若 $A$ 和 $B$ 都是正确的序列，则 $AB$ 也是正确的； - 若 $A$ 是正确的序列，则 ( $ _{i} $ A) $ _{i} $（即以第 $i$ 类括号成对包围 $A$）也是正确的，其中第 $i$ 类括号是成对出现的左、右括号。

第一行是一个整数 $0 < n \leq 1000$，表示测试用例的个数。接下来的 $n$ 行，每行描述一个测试用例。每行首先是一个整数 $0 < m \leq 100$，表示不同类型的括号数量。接下来是 $m$ 个正整数 $k_1, k_2, \ldots, k_m$，每个整数用空格分隔。$k_i$ 表示第 $i$ 类括号对的数量。所有括号对的总和不超过 1000。

对于每个测试用例，输出一个整数——用来表示满足条件的正确括号序列数量对 1000000007 取模的结果。 **本翻译由 AI 自动生成**