归并排序（Merge sort）是最著名的排序算法之一。在本题中，我们使用以下伪代码描述的实现方式：

算法：归并排序算法的实现。

1: function MERGESORT(p, n) ▷ 返回列表 p = [p[0], p[1], . . . , p[n − 1]] 的排序版本。
2: if n = 1 then
3: return p
4: left ← MERGESORT([p[0], . . . , p[⌈n/2⌉ − 1]], ⌈n/2⌉)
5: right ← MERGESORT([p[⌈n/2⌉], . . . , p[n − 1]], ⌊n/2⌋)
6: (i, j) ← (0, 0)
7: result ← [] ▷ [] 表示空列表。
8: while i < |left| and j < |right| do ▷ |left|, |right| 分别为列表 left, right 的长度。
9: if left[i] < right[j] then
10: 将值 left[i] 追加到列表 result 的末尾。
11: i ← i + 1
12: else
13: 将值 right[j] 追加到列表 result 的末尾。
14: j ← j + 1
15: 将值 left[i], . . . , left[|left| − 1] 追加到列表 result 的末尾。
16: 将值 right[j], . . . , right[|right| − 1] 追加到列表 result 的末尾。
17: return result

给定数字 $n, a, b$。你的任务是计算有多少个 $1$ 到 $n$ 的排列，使得在对该排列使用 MERGESORT 过程进行排序时，第 9 行至少执行过一次 $a$ 和 $b$ 的比较。输出该排列数量除以 $1\,000\,000\,007$ ($10^9 + 7$) 的余数。

注意，如果 $a$ 和 $b$ 在 MERGESORT 过程的任何递归调用中被比较，则该排列应被计入，而不一定非要在最浅层的调用中比较。同时请注意，我们允许以任何顺序比较数字 $a$ 和 $b$。换句话说，只需检查 $a < b$ 或 $b < a$ 中的任意一个条件即可计入该排列。

此外，你需要解决多个测试用例。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10\,000$)，表示测试用例的数量。 接下来的 $t$ 行包含连续的测试用例描述。第 $i$ 行包含三个整数 $n, a, b$ ($2 \le n \le 1\,000\,000; 1 \le a, b \le n; a \neq b$)，如题目所述。

输出格式

输出应包含 $t$ 行。第 $i$ 行应包含一个整数，即第 $i$ 个测试用例中符合条件的排列数量除以 $10^9 + 7$ 的余数。

样例

输入 1

3
4 2 3
5 4 1
3 1 3

输出 1

24
52
4

说明

在第一个测试用例中，数字 2 和 3 会在长度为 4 的所有排列的排序过程中被比较。

在第三个测试用例中，我们会在对排列 $[1, 2, 3], [1, 3, 2], [2, 1, 3]$ 和 $[3, 1, 2]$ 进行排序时比较数字 1 和 3。