题目背景

一年一度的括号巡游即将开始。巡游队伍中有若干种不同样式的成对括号，每一种样式都有规定的数量。为了让整支队伍排列得井然有序，所有括号必须组成一个合法括号序列。

请计算一共有多少种不同的排列方案。

题目描述

共有 $m$ 种不同类型的括号，第 $i$ 种括号有 $k_i$ 对，其左括号和右括号分别记作 $(_i$ 与 $)_i$。

一个括号序列被称为合法括号序列，当且仅当它可以由以下规则递归生成：

1. 空序列是合法括号序列；
2. 若 $A$ 和 $B$ 都是合法括号序列，则 $AB$ 也是合法括号序列；
3. 若 $A$ 是合法括号序列，则 $(_iA)_i$ 也是合法括号序列，其中 $(_i$ 和 $)_i$ 是同一种类型的左、右括号。

你必须恰好使用第 $i$ 种括号 $k_i$ 对。求能够组成的不同合法括号序列数量。

由于答案可能很大，请输出答案对 $1\,000\,000\,007$ 取模后的结果。

输入格式

第一行包含一个整数 $T$，表示测试用例数量。

接下来 $T$ 行，每行描述一个测试用例：

• 第一个整数为 $m$，表示括号类型数；
• 接下来 $m$ 个正整数 $k_1,k_2,\ldots,k_m$，其中 $k_i$ 表示第 $i$ 种括号的对数。

输出格式

对于每个测试用例，输出一行一个整数，表示满足要求的不同合法括号序列数量对 $1\,000\,000\,007$ 取模后的结果。

样例输入

3
1 4
2 2 2
3 1 2 3

样例输出

14
84
7920

样例说明

• 第一组数据只有一种括号，共 $4$ 对，合法序列数为第 $4$ 个 Catalan 数，即 $14$；
• 第二组数据共有 $4$ 对括号。忽略类型时有 $14$ 种结构，再从 $4$ 个匹配括号对中选择 $2$ 对作为第一种类型，因此答案为 $14\times\binom{4}{2}=84$；
• 第三组数据共有 $6$ 对括号，答案为

数据范围

对于所有测试数据：

• $1\le T\le 1000$；
• $1\le m\le 100$；
• $k_i\ge 1$；
• 对于每个测试用例，$\displaystyle\sum_{i=1}^{m}k_i\le 1000$。