Onix

모두가 알고 있듯이, 포켓몬 시리즈와 게임에 나오는 돌 뱀 Onix는 싸움이 끝날 때마다 Poké Ball 안으로 다시 숨는다. 그러나 공의 내부가 어떤지는 잘 알려져 있지 않다. 오크 교수는 Onix의 공 내부를 Onix가 몸을 말아 넣는 정사각형으로 나타낼 수 있다는 사실을 밝혀냈다. Onix의 레벨에 따라 필요한 공간이 더 넓거나 좁으므로, 몸을 마는 방법도 여러 가지다.

$N$레벨 Onix의 몸은 $N^2$개의 마디로 이루어져 있다. 정사각형은 $N \times N$개의 작은 칸으로 나뉜다. Onix는 몸의 연속된 마디가 항상 인접한 칸에 놓이도록 몸을 말고, 머리는 항상 왼쪽 위 칸에, 꼬리 끝은 항상 왼쪽 아래 칸에 둔다. 아래 그림은 3레벨 Onix가 공 안에 들어가는 한 가지 방법이다.

가끔 Onix는 등이 아파서 자세를 바꾼다. 과제는 $N$레벨 Onix가 취할 수 있는 서로 다른 자세의 수를 구하는 것이다.

입력은 한 줄이며, Onix의 레벨 $N$ ($1 \le N \le 8$)이 주어진다.

$N$레벨 Onix가 취할 수 있는 서로 다른 자세의 수를 정수 하나로 한 줄에 출력한다.