数木棒

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

假设在一水平线上有N根木棒,木棒高度的取值区间为[1,N],且这N根木棒的所有取值能构成[1,2,..N]的一个排列。

现在假设你从左边看去能看见X根木棒,从右边看去能看见Y根木棒,举个例子:

比如N=4,假设木棒按照高度的一个排列为  1 4 2 3  ,那么从左看去能看见高度为1 4 的两根木棒,(高度为23的看不到,因为其被高度为4的挡住了)。从右看去能看见高度为3 4的两根木棒(高度为2的木棒看不到,因为其被高度为3的木棒挡住了,同理高度1的被高度4的木棒挡住了)。所以在这种情况下:

X=2,Y=2

当然这只是满足条件的一个排列,也可能还存在其他满足条件的高度排列。

现在你的任务是:给定如上所述的N,X,Y。求满足条件的排列的方案数。结果可能会很大,所以只需要输出对1000000007取模的值即可。

Input

第一行输入一个数T,代表下面共有T组测试数据。(T<=100000) 针对每组测试数据:首先输入三个数 N M P (1<=N<=100,1<=M,P<=1000000000) X=SOLVE(M)%N+1 Y=SOLVE(P)%N+1 (%为取模运算符),其中SOLVE函数的定义如下: int SOLVE(int m) { if(m==1) return 0; if(m%2==0) return SOLVE(m/2)+1; else return SOLVE(3*m+1)+1; }

Output

针对每组测试数据,输出相应的答案。

Sample Input

2
1 2 2
1 1 1

Sample Output

1
1

Hint

Source

from friend

提交代码