Queue
There are some people standing in a line. Some people are leaving the line. More specifically, every second, the following happens.
The remaining people are enumerated from 1 to m from left to right where m is the number of people in the line.
One person leaves the line. It may be either the person number l or the person number m - r + 1 where l and r are some constants. Note that one of the options above may not be possible if l > m or r > m. However, the constraints will guarantee that at least one of the options is possible.
This process continues for k seconds.
You are given numbers n, l, r and k. Find how many different sets of people could remain after k seconds. Two sets of people are different if and only if there is a person present in one set and not present in the other. Since the answer can be quite big, you must find it modulo 10^9 + 7.
Input
The first line contains one integer T (1 ≤ T ≤ 10^5): the number of test cases.
Each of the next T lines contains integers n, l, r and k (1 ≤ n, l, r, k ≤ 10^18) describing the test cases. It is guaranteed that in each test case k ≤ n - min(l, r) + 1, that is, in each of the k seconds, at least one of the options at step 2 is possible.
Output
Print T lines: the i-th line must contain the answer to the i-th test case modulo 10^9 + 7.