Khoshaf

시간 제한12초메모리 제한512 MB

요약

길이 N이고 각 원소가 [L, R] 범위에 있으며 합이 3으로 나누어떨어지는 연속 부분 배열이 정확히 K개인 배열의 개수를 1e9+7로 나눈 나머지로 구한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 조합론, 수학, 누적 합
정답자: 아직 제출이 없습니다

문제

심사위원들이 앉아서 Khoshaf(살구 주스에 말린 과일을 담근 음료)를 먹어 보고 싶어 했다. 주문하러 식당에 갔는데 남은 한 접시밖에 없다는 것을 알게 되었고, 그래서 문제를 하나 만들기로 했다. 가장 먼저 푼 사람이 이 남은 접시를 가진다.

문제는 다음과 같다. 네 정수 N, K, L, R이 주어질 때, [L, R] 범위의 정수 값을 담고 있으면서 합이 3으로 나누어떨어지는 연속 부분 구간을 정확히 K개 가지는 길이 N 배열의 개수를 세어라. 답은 109 + 7로 나눈 나머지로 출력한다. 부분 구간들은 서로 겹칠 수 있다. 심사위원장이 마지막 접시를 가질 수 있도록 도와줄 수 있는가?

입력

첫 번째 줄에는 테스트 케이스의 개수를 나타내는 정수 T가 주어진다.

각 테스트 케이스는 정수 N, K, L, R (1 ≤ N, K ≤ 104, 1 ≤ L ≤ R ≤ 109)을 담은 한 줄로 이루어진다. 이는 문제에서 설명한 그대로이다.

출력

각 테스트 케이스마다, [L, R] 범위의 정수 값을 담고 있으면서 합이 3으로 나누어떨어지는 연속 부분 구간을 정확히 K개 가지는 길이 N 배열의 개수를 한 줄에 출력한다. 답은 109 + 7로 나눈 나머지로 출력한다.

힌트

첫 번째 테스트 케이스에서, 다음 배열들 중 어느 것이든 합이 3으로 나누어떨어지는 부분 구간을 정확히 두 개 가진다.

[1,2,1] → 부분 구간은 각각 인덱스 [0,1]과 [1,2]인 [1,2]와 [2,1]이다.
[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]

예제1

예제 1
입력
```
3
3 2 1 3
4 3 1 3
5 4 4 8
```
예상 출력
```
6
20
1808
```