#1055. 多边形序列

多边形序列

Description

有一类特殊的多边形我们把它称为直角多边形,指的是该多边形的每一个

内角都为 90度 或 270度,即每一个角都是直角。

表示一个直角多边形的一种方法是使用多边形序列,多边形序列含两种元

素:L表示 90度、R表示 270度。从直角多边形的任意一个角开始,以逆时针的

顺序对角进行顺序排列,绕一圈后所得到的序列便是多边形序列。比如正方形

的序列为LLLL,而如下图所示的图形可表示为LLRLLRLLRLLR。显然,一个直

角多边形有多种表示序列,而一个序列也对应着多个直角多边形。

image 对于一个直角多边形,如果存在一个多边形内的点,使得从这个点可以看

到多边形边上的每一个点,我们认为这个直角多边形是“可观察的”。现在对于

给定的序列长度 n,请问有多少个序列长度为 n 的不同的多边形序列,满足它

所代表的所有直角多边形中,存在一个“可观察的”直角多边形。

Format

Input

包含一个正整数 n。

Output

包含一个正整数,表示种数。

Samples

6
6

Limitation

N<=10^100000