오르내리는 계단의 경로

문제

6번 문제의 오르내리는 계단에서 $n$ 번째 칸에 도착하는 경로를 모두 출력한다. 0번째 칸에서 출발해 한 번에 2칸 또는 3칸을 오르거나 1칸 또는 2칸을 내려갈 수 있고, 한 번 밟은 칸은 다시 밟지 않으며, 0번째 칸보다 아래나 $n$ 번째 칸보다 위로는 갈 수 없다.

경로는 다음 순서로 찾은 순서대로 출력한다. 각 칸에서 다음 칸을 고를 때 2칸 오르기, 3칸 오르기, 1칸 내려가기, 2칸 내려가기 순서로 시도하고, 한 이동으로 갈 수 있는 경로를 모두 찾은 뒤에 다음 이동을 시도한다.

입력

첫째 줄에 정수 $n$ 이 주어진다.

출력

경로마다 한 줄에 밟은 칸 번호를 0부터 순서대로 공백 한 칸씩으로 구분해 출력한다. 마지막 줄에 경로의 개수를 출력한다. 경로가 없으면 0 한 줄만 출력한다.

제한

$1 \le n \le 12$

입출력 예시

입력 1

출력 1

입력 2

출력 2