题目描述

一个 $n\times n$ 的棋盘，在其中填入 $1$ 和 $-1$。经过一次变换后，方格里的每个数将会变成变换之前与之相邻的四个数的积。例如：

但有一些状态，变换前和变换后是一样的，例如全部是 $1$ 的状态。这种状态被称为不变状态。

你的任务是要找到所有本质不同的不变状态（旋转或翻转之后的状态被视为是本质上相同的）。

输入格式

一行一个正整数 $n$。

输出格式

一行一个正整数表示所有本质不同的方案数。

4

5

提示

$1\le n\le 30$。

题目给出范围内，不变状态总数 $<9\times 10^3$。