画弦
题号:NC23754
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 128 M,其他语言256 M
64bit IO Format: %lld

题目描述

圆周上有n个点,现在要你连n1条弦,使得任意两条弦在圆内互不相交,且最终形成一棵树,求方案数对10^9+7取模的结果。两种方案不同当且仅当存在一条边只属于其中一种方案。

输入描述:

一行一个整数n(n<=5000),表示圆周上点的个数。

输出描述:

一行一个整数,表示方案数对10^9+7取模后的结果。
示例1

输入

复制
4

输出

复制
12
示例2

输入

复制
500

输出

复制
147117237