3교시: 수학

짐비는 수학 시간에 우박수열에 대해 배운 뒤, 길이가 $N$인 우박수열 $A_1, A_2, A_3, ... , A_N$을 만들려고 합니다. 우박수열은 다음 조건을 만족하는 수열 $A$를 의미합니다.

• $1 \leq i \lt N$인 양의 정수 $i$에 대하여, $A_i$가 짝수라면 $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$이 주어질 때, 가능한 우박수열들의 개수를 구하고, 가능한 우박수열들의 첫번째 원소 $A_1$을 오름차순으로 출력해주세요.

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

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

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