题目描述

小明要把一根木头切成两段，然后拼接成一个直角。

如下图所示，他把中间部分分成了 $n×n$ 的小正方形，他标记了每个小正方形属于左边还是右边。然后沿两边的分界线将木头切断，将右边旋转向上后拼接在一起。

要求每个小正方形都正好属于左边或右边，而且同一边的必须是连通的。在拼接时，拼接的部位必须保持在原来大正方形里面。

请问，对于 $n×n$ 的小正方形，有多少种合法的划分小正方形的方式。

输入描述

第一行包一个整数 $n$。

输出描述

对每个输入输出一个整数表示答案。

2

4

3

8

评测用例规模与约定：

对于所有评测用例，$1≤n≤10$。

提示

先想清楚，能够拼接成功的划分，应该满足什么性质。可以尝试画出 $n=2,n=3$。从小 $case$ 中寻找规律也是解决大问题的好的出发点。