비밀번호 timer 1s memory 64MB

1번부터 B번까지의 번호가 붙은, B개의 버튼을 가진 금고가 있다.

이를 통해 금고를 안전하게 보관하기 위한 비밀번호를 만들고자 한다.

비밀번호는 다음과 같이 만들어진다. * 여러 번에 거쳐 버튼을 누를 수 있다. * 한 번에 여러 개의 버튼을 누를 수 있다. * 한번 누른 버튼은 더 이상 사용하지 않는다. * 꼭 모든 버튼을 사용할 필요는 없다, 하지만 아무 단추라도 한번이상은 눌러야 비밀번호로 인정된다.

예를 들어 B = 8일 경우, 다음과 같은 조합은 가능하다. (1-2-3)(4)(7-8)

앞의 예제는 처음에 1,2,3번을 동시에 누르고, 그다음 4번을 누르고, 마지막으로 7,8 번을 동시에 누르는 경우를 말한다.

같은 괄호안에 이음선으로 연결되어 있는 숫자는 동시에 각 숫자를 누른다는 뜻이다. 위의 예제에선 5와 6번이 쓰이지 않았다. 하지만 다음의 경우 2가 두 번 등장하기 때문에 불가능하다. (1-2-3)(2-4)(5-6)

B가 주어졌을 때, 가능한 비밀번호의 모든 경우의 수를 출력하는 프로그램을 작성하라.