度度熊与组题

沃老师在出比赛的题目时遇到麻烦啦！

遇到的麻烦如下：

现在沃老师手上有 $2n$ 道题，题目编号由 $1 \sim 2n$，已知第 $i$ 道题难度为 $a_i$，这些题的难度还满足当 $i<j$ 时 $a_i \le a_j$。现在沃老师想把这些题目分在两套比赛上，每套比赛会被分到 $n$ 道题，每道题都会恰出现在其中一场比赛中。假设分配完后，第一套题难度第 $i$ 小的题的难度为 $c_i$ (第 $i$ 小是指不去重的的第 $i$ 小，例如有四道题难度分别是 $1,1,2,3$ 时，难度第 $3$ 小的题是难度是 $2$)，第二套题难度第 $i$ 小的题为 $d_i$，沃老师定义两场比赛的难度相似度为 $\sum_{i=1}^n{|c_i-d_i|}$，且沃老师希望分配完题目后，两场比赛的难度相似度尽可能的小。

看到这你可能会觉得这算什么麻烦，难度相似度的最小值不就是 $\sum_{i=1}^n (a_{2i}-a_{2i-1})$ 嘛？

是的，光是要使难度相似度最小并不构成沃老师的麻烦，但沃老师是个好奇宝宝，他还想知道，有多少种分配题目的方式，能使难度相似度最小呢？这个问题可能就没那么简单了。

于是沃老师就来拜托聪明的度熊帮他解决他心中的困惑，各位也帮忙算算吧。

请输出分配题目的方式数量除以 $10^9+7$ 的余数。

两种分配方式 $A$ 和 $B$ 不同当且仅当存在某道题出现在 $A$ 的第一套比赛中，却没有出现在 $B$ 的第一套比赛中。举例来说，当 $n = 1$ 时，第一套比赛含有题目 $1$ 第二套比赛含有题目 $2$ 和 第一套比赛含有题目 $2$ 第二套比赛含有题目 $1$ 是不同的。

有多组询问，第一行包含一个正整数 $T$ 代表有几组询问，接着每组测试数据占 $2$ 行，第一行包含一个正整数 $N$，第二行包含 $2N$ 个正整数 $a_1, a_2, \ldots, a_{2N}$。

* $1 \le T \le 2 \times 10^4$
* $1 \le N \le 10^5$
* $1 \le a_i \le 2 \times N$
* 对于不同的正整数 $i,j$，若 $i<j$，则 $a_i \le a_j$
* 所有询问的 $N$ 的总和不超过 $10^6$

对于每一个询问。输出一个非负整数代表答案除以 $10^9+7$ 的余数。

5
2
1 2 2 4
2
1 2 3 4
1
1 1
1
1 2
6
9 9 9 10 10 10 11 11 11 12 12 12

6
4
2
2
324

Note
令 day1 是第一套比赛的题目题号集合，day2 是第二套比赛的题目题号集合。

在第一组询问中，全部六种组合难度相似度都是 $3$，故答案为 $6$。

在第二组询问中难度相似度最小为 $2$，有四种可能分配方式如下：

1. day1:$\{1,3\}$,day2:$\{2,4\}$
2. day1:$\{1,4\}$,day2:$\{2,3\}$
3. day1:$\{2,3\}$,day2:$\{1,4\}$
4. day1:$\{2,4\}$,day2:$\{1,3\}$

2019 年百度之星·程序设计大赛 - 初赛二