DreamGrid 有一个 $1, 2, \dots, n$ 的有趣排列，记作 $a_1, a_2, \dots, a_n$。他根据排列 $a$ 生成了三个长度均为 $n$ 的序列 $f, g$ 和 $h$，生成方式如下：

• 对于每个 $1 \le i \le n$，$f_i = \max\{a_1, a_2, \dots, a_i\}$；
• 对于每个 $1 \le i \le n$，$g_i = \min\{a_1, a_2, \dots, a_i\}$；
• 对于每个 $1 \le i \le n$，$h_i = f_i - g_i$。

BaoBao 刚刚发现了 DreamGrid 生成的序列 $h$，并决定还原出原始的排列。给定序列 $h$，请帮助 BaoBao 计算有多少种不同的排列可以生成该序列 $h$。由于答案可能很大，请输出答案对 $10^9 + 7$ 取模的结果。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 20\,000$)，表示测试数据的组数。

对于每组测试数据，第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示排列及序列的长度。第二行包含 $n$ 个整数 $h_1, h_2, \dots, h_n$ ($1 \le i \le n, 0 \le h_i \le 10^9$)。

保证所有测试数据的 $n$ 之和不超过 $2 \cdot 10^6$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示可以生成给定序列 $h$ 的不同排列的数量。请记得将答案对 $10^9 + 7$ 取模。

样例

样例输入 1

3
3
0 2 2
3
0 1 2
3
0 2 3

样例输出 1

2
4
0

说明

对于第一个样例，排列 $\{1, 3, 2\}$ 和 $\{3, 1, 2\}$ 都可以生成给定的序列。

对于第二个样例，排列 $\{1, 2, 3\}, \{2, 1, 3\}, \{2, 3, 1\}$ 和 $\{3, 2, 1\}$ 都可以生成给定的序列。