405551: GYM101991 K Khoshaf

Memory Limit:1024 MB Time Limit:12 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

K. Khoshaftime limit per test12 secondsmemory limit per test1024 megabytesinputkhoshaf.inoutputstandard output

The judges were sitting and they wanted to try Khoshaf (Mix of dried fruits soaked in Apricot juice). They went to a restaurant to order it, however, they found that there is only one dish remaining, so they decided to make a problem, and the first to solve it will have this remaining dish.

The problem is as follows: Given four integers N, K, L, and R, count the number of arrays of length N that contains integer values within the range [L, R] inclusively and has exactly K continuous sub-intervals with sum divisible by 3. The output answer should be taken modulo 109 + 7. Please note that the sub-intervals may overlap. Can you help the chief judge to have the final dish?

Input

The first line contains a single integer T specifying the number of test cases.

Each test case consists of a single line containing four integers N, K, L, and R (1 ≤ N, K ≤ 104, 1 ≤ L ≤ R ≤ 109), as described in the problem statement.

Output

For each test case, print a single line containing the number of arrays of length N that contains integer values within the range [L, R] inclusively and has exactly K continuous sub-intervals with sum divisible by 3. The output answer should be taken modulo 109 + 7.

ExampleInput
3
3 2 1 3
4 3 1 3
5 4 4 8
Output
6
20
1808
Note

In the first test case, any of the following arrays will contain exactly two sub-intervals whose sums are divisible by 3:

[1,2,1] The sub-intervals are [1,2] and [2,1] with indices [0,1] and [1,2] respectively.

[1,3,2] [3], [1,3,2]

[2,1,2] [2,1], [1,2]

[2,3,1] [3], [2,3,1]

[3,1,3] [3], [3]

[3,2,3] [3], [3]

加入题单

上一题 下一题 算法标签: