노래에서도 말하듯, 슬픈 세 번째 막은 하지 않겠다. 하지만 그 노래는 슬프니, 즐거운 노래 하나를 떠올려 보자.

Šnenokle가 무엇인지 아는가? Šufnudle는? Pihtije는? Knaput는?

Malnar 씨는 알고 있지만, 다음 문제를 푸는 데 도움이 필요하다.

짝수인 자연수 $N$이 주어진다. $\{0,1,\ldots,2^N-1\}$의 부분집합 $S$에서 두 원소를 고른 모든 $\binom{|S|}{2}$개의 쌍의 비트 XOR 값이 서로 다르면, 이 집합을 배고픈 집합이라고 한다. 가능한 한 큰 배고픈 집합을 찾아라.

입력

입력의 유일한 줄에는 문제에서 설명한 자연수 $N$이 주어진다.

출력

첫 번째 줄에는 여러분의 배고픈 집합에 속한 원소의 수를 출력하라.

두 번째 줄에는 집합의 원소들을 공백으로 구분하여 출력하라.

서브태스크

어떤 서브태스크에서 크기가 $t$인 배고픈 집합을 출력했다면, 해당 서브태스크에서 여러분의 풀이가 받는 점수는 다음 식으로 결정된다.

$$ \operatorname{점수}(t)= \begin{cases} 2.4\cdot\frac{t}{t_1} & t<t_1,\\ 2.4+3.6\cdot\frac{t-t_1}{t_2-t_1} & t_1\le t<t_2,\\ 6+12\cdot\frac{t-t_2}{t_3-t_2} & t_2\le t<t_3,\\ 20 & t_3\le t. \end{cases} $$

각 서브태스크의 점수는 소수점 아래 두 자리까지 반올림된다. 총점은 서브태스크별 점수의 합이며, 이 역시 소수점 아래 두 자리까지 반올림된다.

소스 코드의 크기는 최대 1 MiB이다.

예제

입력 1

4

출력 1

6
0 1 2 4 8 15