Start 2023-11-11 08:00:00

20231111卡特兰数专题

End 2023-11-12 22:00:00
Contest is over.
Now 2026-11-19 00:40:20

A. 凸多边形的三角形剖分

Description

若干条互不相交的对角线,把这个多边形剖分成了若干个三角形,现在的任务是输入凸多边形的边数n,求不同剖分的方案数Cn。比如当n=5时,如图4.9所示,有如下5种不同的方案,所以C5=5。 图4.9

Input

一个整数n(n≤100)。

Output

一个整数,即方案数。

Examples

Input

5

Output

5

Submit

Login

Signup
Time Limit 1 second
Memory Limit 128 MB
Submit