Little Z is a famous architect. One day, he received a very strange task: to build $n$ buildings on a number line, where the height of each building is an integer between $1$ and $n$. Little Z has severe obsessive-compulsive disorder, so he does not like any two buildings to have the same height. Additionally, Little Z feels that a group of buildings has a unique aesthetic if, when looking from the far left (with all buildings to the right), one can see $A$ buildings, and when looking from the far right (with all buildings to the left), one can see $B$ buildings. Now, Little Z wants to know how many building arrangements satisfy all the above conditions.

A building $i$ can be seen from the left (or right) if no building to its left (or right) is taller than it. Two arrangements are considered different if and only if there exists at least one building that has a different height in the two arrangements.

Input

The first line contains an integer $T$, representing the number of test cases. Each of the next $T$ lines contains three integers $n, A, B$.

Output

For each test case, output the answer modulo $10^9 + 7$ on a single line.

Constraints

• $10\%$: $1 \le n \le 10$
• $20\%$: $1 \le n \le 100$
• $40\%$: $1 \le n \le 50000$, $1 \le T \le 5$
• $100\%$: $1 \le n \le 50000$, $1 \le A, B \le 100$, $1 \le T \le 200000$

Examples

Input 1

2
3 2 2
3 1 2

Output 1

2
1