문제
0과 1로 이루어진 수열 S가 주어진다. S의 첫 수를 s_1, 마지막 수를 s_N이라고 할 때, S의 인접한 비트의 개수는 다음과 같이 구할 수 있다.
s_1 x s_2 + s_2 x s_3 + s_3 x s4 + ... + s(N-1) x s_N
위의 식을 이용하면 수열 S에서 인접한 1의 개수를 구할 수 있다. 예를들어, 011101101의 인접한 비트의 개수는 3이 되고, 111101101은 4, 010101010은 0이 된다.
수열 S의 크기 N과 K가 주어졌을 때, 인접한 비트의 개수가 k인 수열 S의 개수를 구하는 프로그램을 작성하시오.
예를 들어, N이 5이고, K가 2이면, 수열 S가 될 수 있는 수열은 다음과 같이 6가지가 있다.
11100
01110
00111
10111
11101
11011
입력
첫 번째 줄에 테스트 케이스의 수 T가 주어진다. (1 ≤ T ≤ 1,000)
각 테스트 케이스의 첫 번째 줄에 세 정수 t, N, K가 공백으로 분리되어 주어진다. t는 테스트 케이스의 번호이다. (1 ≤ N ≤ 100)
출력
각 테스트 케이스에 대해 테스트 케이스 번호와 인접한 비트의 개수가 k인 수열 S의 개수를 사이에 공백을 두고 한 줄에 하나씩 출력한다.
이 값은 2,147,483,647보다 작거나 같다.
힌트
예제 입력
10
1 5 2
2 20 8
3 30 17
4 40 24
5 50 37
6 60 52
7 70 59
8 80 73
9 90 84
10 100 90
예제 출력
1 6
2 63426
3 1861225
4 168212501
5 44874764
6 160916
7 22937308
8 99167
9 15476
10 23076518
