题目描述

设有一个凸n边形,可以用n-3条不相交的对角线将n边形分成n-2个互相没有重叠的三角形。

例如n=5,共有下图所示的5种方法。

当给出凸n边形的边数n ,求出共有多少种不同的分法。

输入格式

一个整数n

输出格式

一个整数表示答案

样例

5

5

6

14

数据范围

$n≤1 000$

来源

• 信息学奥赛之数学一本通
• stong9070整理