광고 없는 곡 고르기

문제

음악 스트리밍 서비스의 재생목록에는 n곡이 재생 순서대로 놓여 있다. 운영팀은 이 중 정확히 k곡을 골라 '추천 곡' 표시를 붙이려 한다. 사용자가 피로를 느끼지 않도록 재생 순서에서 바로 이웃한 두 곡에 동시에 표시를 붙일 수는 없다. 재생목록은 두 종류가 있다. 종류 0은 한 번만 재생하는 목록으로, i번째 곡과 i+1번째 곡만 이웃한다. 종류 1은 반복 재생 목록으로, 마지막 곡을 재생한 뒤 첫 번째 곡이 이어서 나오므로 n번째 곡과 1번째 곡도 이웃한다. 종류 1에서는 곡이 3곡 이상인 경우만 주어진다. 곡은 모두 서로 다르므로 선택한 곡의 집합이 다르면 다른 방법이다. 고르지 않는 것(k = 0)도 한 가지 방법으로 센다. 여러 개의 질문이 주어질 때, 각 질문마다 표시를 붙이는 방법의 수를 1,000,000,007로 나눈 나머지를 출력하는 프로그램을 작성하시오. 가능한 방법이 없으면 0을 출력한다. 예를 들어 반복 재생 목록에서 n = 5, k = 2이면 이웃하지 않은 두 곡의 쌍은 5가지이다.

입력

첫 줄에 질문의 수 Q가 주어진다. 이어지는 Q개의 줄에 각각 정수 t, n, k가 공백으로 구분되어 주어진다. t는 목록의 종류(0 또는 1)이다. 1 ≤ Q ≤ 200,000, 1 ≤ n ≤ 200,000, 0 ≤ k ≤ n 이며, t = 1이면 n ≥ 3 이다.

출력

각 질문의 답을 한 줄에 하나씩, 입력 순서대로 출력한다.

3
0 5 2
1 5 2
1 4 2

6
5
2

4
0 1 1
0 3 2
0 3 3
1 3 0

1
1
0
1

출처: Devin.KR 자체 제작