카탈란 조합 객체

Andrew는 카탈란 수를 좋아한다. 또 농담하기를 좋아한다.

그는 경험 많은 문제 출제자로, 훈련 캠프용 대회를 여러 개 준비한다. 대회마다 정수 하나를 입력받아 정수 하나를 출력하는 문제를 하나씩 낸다. 입력 0, 1, 2, 3, 4, 5에 대한 답은 각각 1, 1, 2, 5, 14, 42이다. 하지만 더 큰 입력에 대한 답은 대응하는 카탈란 수와 일치하지 않는다.

Andrew는 이런 성질을 가진 좋은 문제가 모자라서 출제 과정을 자동화하기로 했다. 후보 문제 풀로, 특정한 성질을 가진 조합 객체의 개수를 세는 문제들을 쓴다. 그는 입력 6에 대한 원하는 답으로 $k$를 골랐다. 그리고 가중치가 각각 0, 1, 2, 3, 4, 5, 6인 원소가 1, 1, 2, 5, 14, 42, $k$개인 조합 객체 집합의 설명을 찾고자 한다.

Andrew는 다음 방법으로 조합 객체를 만든다.

기저 집합 $B$는 가중치가 1인 단위 객체 $u$ 하나로 이루어진다. 만들어진 각 객체 $x$는 가중치 $w(x)$를 가진다. 객체가 다른 객체 하나 이상으로 만들어지면, 그 가중치는 구성 요소들의 가중치 합과 같다.

$X$를 조합 객체들의 집합이라 하자. 다음 방법으로 새로운 집합을 만들 수 있다.

집합 $L(X)$는 원소가 $X$에 속하고 가중치가 양수인, 유한 길이의 리스트를 모두 담는다. 예를 들어 $L(B)$에는 $\[]$, $\[u]$, $\[u, u]$, $\[u, u, u]$ 등이 들어 있다. 마찬가지로 $L(L(B))$에는 $\[]$, $\[\[u]]$, $\[\[u], \[u]]$, $\[\[u, u], \[u]]$, $\[\[u], \[u, u]]$ 등이 들어 있다. 리스트에서 원소의 순서가 중요하므로 마지막 두 리스트는 서로 다르다. 또한 $\[\[]]$는 $L(L(B))$에 들어 있지 않다. 리스트에는 가중치가 양수인 객체만 넣을 수 있는데 $\[]$의 가중치는 0이기 때문이다.

집합 $S(X)$는 원소가 $X$에 속하고 가중치가 양수인, 유한 크기의 모든 다중집합을 담는다. 예를 들어 $S(B)$에는 $\{\}$, $\{u\}$, $\{u, u\}$, $\{u, u, u\}$ 등이 들어 있다. $S(L(B))$에는 $\{\[u]\}$, $\{\[u], \[u]\}$ 같은 집합이 들어 있다. 다중집합에는 같은 원소가 여러 번 들어갈 수 있다. 다중집합에서는 순서가 상관없으므로 $\{\[u], \[u, u]\}$와 $\{\[u, u], \[u]\}$는 같다.

집합 $C(X)$는 원소가 $X$에 속하고 가중치가 양수인, 유한 길이의 사이클을 모두 담는다. 한 사이클을 순환 이동하여 다른 사이클로 바꿀 수 있으면 두 사이클은 같다. 예를 들어 $C(L(B))$에는 $(\[u], \[u, u], \[u, u, u])$가 들어 있다. 이 객체는 $(\[u, u], \[u, u, u], \[u])$와 같지만 $(\[u, u, u], \[u, u], \[u])$와는 다르다.

리스트, 집합, 사이클의 가중치는 그 원소들의 가중치 합이다. 예를 들어 $(\[u], \[u, u], \[u, u, u])$의 가중치는 6이다.

마지막 구성 방법은 순서쌍이다. $X$와 $Y$가 객체의 집합이면, $P(X,Y)$는 첫 번째 성분이 $X$에서, 두 번째 성분이 $Y$에서 오는 순서쌍의 집합이다. 예를 들어 $P(S(B),L(B))$에는 $\langle\{u, u\}, \[u, u, u]\rangle$와 $\langle\{\}, \[u]\rangle$가 들어 있다. 리스트, 집합, 사이클과 달리 순서쌍의 성분은 가중치가 0이어도 된다.

$k$가 주어질 때, 가중치 0인 원소 1개, 가중치 1인 원소 1개, 가중치 2인 원소 2개, 가중치 3인 원소 5개, 가중치 4인 원소 14개, 가중치 5인 원소 42개, 가중치 6인 원소 $k$개를 포함하는 조합 객체 집합의 설명을 구하라.

입력 파일에는 여러 개의 테스트 케이스가 들어 있다.

각 테스트 케이스는 한 줄에 정수 $k$ 하나로 주어진다($120 \le k < 140$).

입력의 마지막 줄에는 $n = 0$이 주어진다.

각 테스트 케이스마다, 문제에서 설명한 형식에 맞춘 조합 객체 집합의 설명을 한 줄에 출력한다. 설명의 길이는 최대 2000이다. 공백은 출력하지 않는다.