#P1976. 鸡蛋饼

    ID: 927 Type: RemoteJudge 1000ms 125MiB Tried: 0 Accepted: 0 Difficulty: 3 Uploaded By: Tags>洛谷原创卡特兰数,Catalan

鸡蛋饼

题目背景

Czyzoiers 都想知道小 x 为什么对鸡蛋饼情有独钟。经过一番逼问,小 x 道出了实情:因为他喜欢圆。

题目描述

最近小 x 又发现了一个关于圆的有趣的问题:在圆上有 2N2N 个不同的点,小 x 想用 NN 条线段把这些点连接起来(每个点只能连一条线段),使所有的线段都不相交,他想知道这样的连接方案有多少种?

答案对 108+710^{\color{red}\bm 8}+7 取模。

输入格式

一行一个正整数 N (1N2999)N\ (1 \le N \le 2999)

输出格式

一行一个整数表示答案。

答案对 108+710^{\color{red}\bm 8}+7 取模。

24
4057031