You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

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

题目描述

最近小 x 又发现了一个关于圆的有趣的问题：在圆上有 $2N$ 个不同的点，小 x 想用 $N$ 条线段把这些点连接起来（每个点只能连一条线段），使所有的线段都不相交，他想知道这样的连接方案有多少种？

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

输入格式

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

输出格式

一行一个整数表示答案。

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

24

4057031