There are some people standing in a line. Some people are leaving the line. More specifically, every second, the following happens.

1. The remaining people are enumerated from 1 to m from left to right where m is the number of people in the line.
2. 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 109 + 7.

Input

The first line contains one integer T (1 ≤ T ≤ 105): the number of test cases.

Each of the next T lines contains integers n, l, r and k (1 ≤ n, l, r, k ≤ 1018) 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 109 + 7.