문제
정인이네 학교에서는 영어 단어 시험을 볼 예정이다. N개의 단어와 N개의 우리말 뜻이 나열되어 있을 때 그 짝을 맞추는 것이다. 요즘 아이돌에 심취해 있는 정인이는 영어 시험 준비를 하지 못하였다. 그래서 대충 찍을 생각이다. F(n, k)를 n개의 문제에 대하여 정인이가 답을 맞추어 제출할 때 적어도 1번부터 연속하여 k개를 틀리는 경우의 수라고 하자. 다시 말해 1번부터 k개는 모두 틀리고 그 이후의 문제는 어찌되는 상관없는 경우의 수라는 것이다.
예를 들어 3개의 단어와 3개의 우리말 뜻이 주어졌다고 하고 적어도 1번부터 시작하여 1개가 틀리는 경우를 생각해보자.
정답이 1-1, 2-2, 3-3 이라고 할 경우 적어도 1번부터 시작하여 1개가 틀리는 경우는
1-2, 2-1, 3-3 1-2, 2-3, 3-1 1-3, 2-1, 3-2 1-3, 2-2, 3-1 4가지가 있다.
n, k를 입력받아 F(n, k)를 구하는 프로그램을 작성하시오.
입력
첫 행에 테스트 케이스의 수 T(1 ≤ T ≤ 5)가 입력된다.
이어서 T개의 행에 n과 k가 입력된다. (1 ≤ n ≤ 17), (0 ≤ k ≤N)
출력
각 테스트 케이스에 대하여 F(n, k)를 행으로 구분하여 출력하시오. 출력 결과는 263-1 이하이다.
예제
4
4 1
7 3
10 5
17 17
18
3216
2170680
130850092279664
출처
Greater NY
로그인해야 코드를 작성할 수 있어요.