Khoshaf

Time limit12sMemory limit512 MB

Summary

Count arrays of length N with entries in [L, R] that have exactly K contiguous subarrays whose sum is divisible by 3, modulo 1e9+7.

Level: Hard8 of 10
Topics: Dynamic programming, Combinatorics, Math, Prefix sum
Solved: No attempts yet

Problem

The judges were sitting around and wanted to try Khoshaf (a mix of dried fruits soaked in apricot juice). They went to a restaurant to order it, but they found that only one dish remained, 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 contain integer values within the range [L, R] inclusively and have exactly K continuous subintervals with sum divisible by 3. The output answer should be taken modulo 109 + 7. The subintervals 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 contain integer values within the range [L, R] inclusively and have exactly K continuous subintervals with sum divisible by 3. The output answer should be taken modulo 109 + 7.

Hint

In the first test case, any of the following arrays contains exactly two subintervals whose sums are divisible by 3:

[1,2,1] → The subintervals 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]

Examples1

Example 1
Input
```
3
3 2 1 3
4 3 1 3
5 4 4 8
```
Expected output
```
6
20
1808
```