시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
12 초 | 512 MB | 4 | 0 | 0 | 0.000% |
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 subintervals 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?
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.
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.
3 3 2 1 3 4 3 1 3 5 4 4 8
6 20 1808
In the first test case, any of the following arrays will contain exactly two sub-intervals whose sums are divisible by 3: