多边形序列

时间限制:10s      空间限制:256MB

题目描述

有一类特殊的多边形我们把它称为直角多边形,指的是该多边形的每一个
内角都为 90度 或 270度,即每一个角都是直角。
表示一个直角多边形的一种方法是使用多边形序列,多边形序列含两种元
素:L表示 90度、R表示 270度。从直角多边形的任意一个角开始,以逆时针的
顺序对角进行顺序排列,绕一圈后所得到的序列便是多边形序列。比如正方形
的序列为LLLL,而如下图所示的图形可表示为LLRLLRLLRLLR。显然,一个直
角多边形有多种表示序列,而一个序列也对应着多个直角多边形。
对于一个直角多边形,如果存在一个多边形内的点,使得从这个点可以看
到多边形边上的每一个点,我们认为这个直角多边形是“可观察的”。现在对于
给定的序列长度 n,请问有多少个序列长度为 n 的不同的多边形序列,满足它
所代表的所有直角多边形中,存在一个“可观察的”直角多边形。


输入格式

包含一个正整数 n。


输出格式

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


样例输入

6

样例输出

6

提示

N<=10^100000


题目来源

没有写明来源