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$을 한 줄에 하나씩, 오름차순으로 출력해 주세요.