题目描述

Bob 对序列有着严格的要求。他认为一个序列 $s$ 是优美的，当且仅当对于这个序列的所有前缀 $[s_1,s_2,\cdots ,s_i]$，都满足 $s_i$ 是这个前缀的最大值或者最小值。

现在 Bob 有一个序列 $a$，他希望通过重排这个 $a$ 得到优美的序列。但是方案可能有很多，他想问你有多少种本质不同的重排方案，使得重排后的序列是优美的。好心的 Bob 注意到方案可能有很多，所以他只要求你求出答案对 $10^9+7$ 取模的值。

而最近 Bob 成为了序列协会会长，所以他会得到 $T$ 个序列，你需要对每个序列都求出一个答案。

输入格式

第一行一个整数 $T$，表示 Bob 得到的序列个数。

接下来每个序列，共两行。第一行一个正整数 $n$，表示序列长度。第二行共 $n$ 个由空格分隔的正整数，表示这个序列。

输出格式

共 $q$ 行，每行一个正整数。第 $i$ 行的正整数表示第 $i$ 个序列的答案对 $10^9+7$ 取模的值。

3
3
1 2 3
2
1 1
4
1 1 2 3

4
1
7

数据范围

• 对于 $30\%$ 的数据：$\sum n \le 9$。

• 对于 $60\%$ 的数据：$\sum n \le 1000$。

• 对于 $100\%$ 的数据：$\sum n \le 10^6$。

• 对于所有数据，$1 \le T \le 10^3$，$1 \le \sum n \le 10^6$，$0 \le a_i \le 10^9$。