33633번 - 3교시: 수학

문제

짐비는 수학 시간에 우박수열에 대해 배운 뒤, 길이가 $N$인 우박수열 $A_1,$ $A_2,$ $A_3,$ $\cdots,$ $A_N$을 만들려고 합니다.

우박수열은 다음 조건을 만족하는 수열 $A$를 의미합니다:

• 1ドル \leq i \lt N$인 양의 정수 $i$에 대하여, $A_i$가 짝수라면 $\displaystyle A_{i+1}=\frac{A_i}{2},ドル 홀수라면 $A_{i+1}=3A_i+1$입니다.
• $A_N = 1$입니다. 또한, 1ドル \le i < N$이면 $A_i \neq 1$입니다.

$N$이 주어질 때 가능한 길이가 $N$인 우박수열의 개수를 구하고, 가능한 우박수열의 첫 번째 원소 $A_1$을 오름차순으로 출력해 주세요.

입력

첫 번째 줄에 우박수열의 길이를 나타내는 정수 $N$이 주어집니다. $(1 \leq N \leq 55)$

출력

첫 번째 줄에 길이가 $N$인 서로 다른 우박수열의 개수 $k$를 출력해 주세요.

두 번째 줄부터 $k$개의 줄에 걸쳐, 길이가 $N$인 우박수열의 첫 번째 원소 $A_1$을 한 줄에 하나씩, 오름차순으로 출력해 주세요.

제한

힌트