두 정수 n, k가 주어졌을 때, 집합 {1, 2, ..., n}을 k개의 부분집합으로 나누는 모든 경우의 수를 출력하시오.

이때 각 부분집합은 서로소이고, 공집합이 아니어야 하며, 모든 부분집합의 합집합은 원래 집합 {1, 2, ..., n}이 되어야 한다.

이때 부분집합들의 순서만 다른 것은 같은 것으로 취급된다.


-- 더 쉬운 문제 설명 --

어떤 반에 학생이 n명이 있다. 그 반의 학생들을 번호순으로 1, 2, 3, ..., n 으로 불러 보자.

그 학생들을 k개의 그룹으로 나눠 보자. 각 그룹에는 적어도 1명 이상의 학생은 속해야 할 것이다.

이때 가능한 그룹의 모든 경우를 구하면 된다. 단, 그룹의 순서만 다른 것 (e.g. [{1, 2}, {3, 4}] vs [{4, 3}, {1, 2}]) 은 같은 것으로 취급해야 한다.


ex)


n = 4, k = 2 일 때,

{1, 2, 3, 4} 를 나눌 수 있는 경우는

1. {1}, {2, 3, 4}

2. {2}, {1, 3, 4}

3. {3}, {1, 2, 4}

4. {4}, {1, 2, 3}

5. {1, 2}, {3, 4}

6. {1, 3}, {2, 4}

7. {1, 4}, {2, 3}


이렇게 7가지 있다.


tip: n이 커질수록 경우의 수도 엄청나게 커지니까 (n = 16, k = 8일 때 경우의 수가 2141764053) 숫자가 엄청 크게 나와도 그게 정상임