프로보즈 열쇠회사는 푸쉬버턴 열쇠를 만들어 비지니스를 하고 있다. 푸쉬버턴 락 은 1 에서 B( 1 <= B <= 11) 까지의 번호로 이루어져 있다.

열쇠는 일련의 버턴 조합이 맞는다면 , 열쇠는 자동으로 열린다.

조합이란 하나 혹은 그 이상의 버턴이 동시에 눌려 진다는 것을 의미한다. 나열은 일련의 조합으로 이루어진다. 나열은 적어도 하나이상의 조합으로 구성이 되어야 하고 , 어떤 번호가 조합에서 사용되었다면 다른 조합에서 이 버턴을 사용하면 안되고, 또한 나열에서 모든 버턴을 사용할 필요는 없다.

예로 , B = 8 이라면

(1-2-3)(4)(7-8)

(1-2-3)(2-4)(5-6)

예로 , B 가 3 일 경우 나올수 있는 가짓수는 총 25 가지이다.

--한 가지 조합
1. (1)
2. (2)
3. (3)
4. (1,2)
5. (1,3)
6. (2,3)
7. (1,2,3)
   --두 가지 조합
8. (1) (2)
9. (2) (1)
10. (1) (3)
11. (3) (1)
12. (2) (3)
13. (3) (2)
14. (1,2) (3)
15. (3) (1,2)
16. (1,3) (2)
17. (2) (1,3)
18. (2,3) (1)
19. (1) (2,3)
    --세 가지 조합
20. (1)(2)(3)
21. (1)(3)(2)
22. (2)(1)(3)
23. (2)(3)(1)
24. (3)(1)(2)
25. (3)(2)(1)

입력

출력

출력 형식은

순서번호 구할수 가짓수

입출력 예

입력

3
3
4
3

출력

1 3 25
2 4 149
3 3 25

출처:Greater New York 2006