#1780. 凸多边形的三角形剖分

凸多边形的三角形剖分

题目描述

传说魔法世界的创世神使用过的一件上古神器遗失在一个凸多边形的二维魔法空间中,谁若拥有这件上古神器,将会成为世界之主。修罗王很想拥有这件上古神器,他打算通过若干条互不相交的对角线,把这个多边形剖分成了若干个三角形来寻找,现在的任务是输入凸多边形的边数n\red{n},求不同剖分的方案数Cn\red{C_n}。比如当n=5\red{n=5}时,如图所示,有如下5\red{5}种不同的方案,所以C5=5\red{C_5=5}

img

输入格式

一个整数n\red{n}

输出格式

一个整数,即方案数。

样例

输入样例

5

输出样例

5