큰 파티
시간 제한1초메모리 제한1024 MB
원탁에 남녀 N명이 앉는 방법 중 회전으로 겹치는 배치는 하나로 보고, 여자가 K명을 넘게 연속으로 앉지 않는 경우의 수를 구합니다.
문제
이레나와 시루프는 다음 주말에 약혼 파티를 열 예정이다. 거의 모든 사람을 초대하고 싶다. 이 자리를 위해 아주 큰 원탁을 막 구입했다. 하지만 사람들을 원탁에 어떻게 배치할지 고민하고 있다. 이레나는 여자가 K명보다 많이 옆으로 연달아 앉으면 그 무리가 밤새 함께 떠들며 다른 사람과는 대화하지 않을 것이라고 주장했다.
시루프는 그 말에 동의할 수밖에 없었다. 그러나 수학자인 그는 원탁에 앉는 남자와 여자의 모든 가능한 배치 패턴에 금세 흥미를 느꼈다.
원탁에는 N명이 앉는다. 그중 일부는 남자이고 나머지는 여자이다.
여자가 K명을 넘게 옆으로 연달아 앉지 않도록 남자와 여자에게 자리를 배정하는 방법의 수를 세는 것이 과제이다.
모든 사람을 회전시켜 한 배정에서 다른 배정을 만들 수 있다면, 두 배정은 같은 것으로 보고 한 번만 센다.
입력
입력 파일의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스 앞에는 빈 줄이 하나 있다.
각 테스트 케이스의 입력은 두 정수 N과 K가 적힌 한 줄이다.
출력
각 테스트 케이스마다 사람들을 원탁에 배치하는 방법의 수를 100000007로 나눈 나머지를 한 줄에 정수 하나로 출력한다.
제한
1 ≤ T ≤ 20
힌트
첫 번째 테스트 케이스에서 가능한 경우는 두 가지이다. MMM 또는 MMW이다 (M은 남자, W는 여자).
두 번째 테스트 케이스에서는 두 가지가 더 있다. MWW와 WWW이다.
세 번째 테스트 케이스에서 가능한 경우는 세 가지이다. MMMM, MMMW, MWMW이다.