UOJ Logo Universal Online Judge

UOJ

#12. 卡特兰数

统计
卡特兰数是这样的一列数:1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786,...以比利时的数学家来命名。

问题描述

一个凸N边形(n>3),通过N边形内部互不交互的对角线,把N边形划分成若干个三角形。求不同的拆分数用H(N)表示。

输入描述

一个整数n (n<500)

输出描述

一个整数H(n),这个数对100000007求余。

输入样例

5

输出样例

5

样例图