#P4201. 多边形序列

    ID: 3416 传统题 1000ms 256MiB 尝试: 25 已通过: 5 难度: 9 上传者: 标签>CF2600提高+/省选-双射计数贡献法高精度乘法卷积转化NTT中国剩余定理高精度减法高精度除法

多边形序列

题目描述

有一类特殊的多边形我们把它称为直角多边形,指的是该多边形的每一个内角都为 90∘90^\circ 或 270∘270^\circ,即每一个角都是直角。

表示一个直角多边形的一种方法是使用多边形序列,多边形序列含两种元素:L 表示 90∘90^\circ、R 表示 270∘270^\circ。从直角多边形的任意一个角开始,以逆时针的顺序对角进行顺序排列,绕一圈后所得到的序列便是多边形序列。比如正方形的序列为 LLLL,而如下图所示的图形可表示为 LLRLLRLLRLLR。显然,一个直角多边形有多种表示序列,而一个序列也对应着多个直角多边形。

image

对于一个直角多边形,如果存在一个多边形内的点,使得从这个点可以看到多边形边上的每一个点,我们认为这个直角多边形是「可观察的」。现在对于给定的序列长度 nn,请问有多少个序列长度为 nn 的不同的多边形序列,满足它所代表的所有直角多边形中,存在一个「可观察的」直角多边形。

输入格式

包含一个正整数 nn。

输出格式

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

样例

6
6

数据规模与约定

对于 100%100\% 的数据,n≤10105n \le 10^{10^5}。