文理学院程序设计在线练习


传送魔法

Time Limit: 10 Second(s)    Memory Limit: 128 MB

Total Submission(s): 26   Accepted Submission(s): 12
Problem Description

哈利波特掌握了一种神奇的传送魔法,这可以让他完成任意距离的瞬移,然而魔法学院的校长邓布利多对他的移动做了一定的限制,让他只能在1到n的整点位置移动,同时在位置b处设下法阵,使得哈利波特的每次移动目的地y与出发点x之间的关系必须满足|x-b|>|x-y|,经过了这样的限定,哈利波特的移动方式就变得非常的有限,这个他想知道他从a点出发,经过k次移动一共能有几种移动方式,我们认为,在移动中产生的序列有一位不同则可视为不同的移动方式,在传送中,出发点与目的点不能相同,但是答案还是非常庞大,因此需要你对1000000007取模之后再输出。

Input

第一行一个数字T(T ≤ 10)表示数据组数;
接下来每行四个数字 n , a , b , k(1 ≤ n , k ≤ 5000, 1 ≤ a, b ≤ n) , 含义如上所述。

Output

每组数据输出一行,移动方式数对1000000007取模。

Sample Input
1                          
5 2 4 2
Sample Output
2
Hint

对于样例,两种传送方式为2—1—2和2—1—3

Source

第12届校赛