题号：NC22755
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld
题目描述
小西和小理一直pk也很累了，他们找到了一个卖饼的大叔，但是大叔卖的饼都是奇怪的不规则凸多边形，小西和小理想到了一个办法把饼平分：
沿着多边形几条不相交的对角线将饼分割成一个个三角形，再把每个三角形沿着中线切开，就可以完美的把饼平分了。
但是在分饼的过程中，小西和小理又吵了起来——把饼分割成三角形的方法可是太多了！小西和小理对于分割方法的数目各执一词，聪明的你能告诉他们正确答案吗？
例如五边形饼有以下五种分法：
输入描述:
有多组输入。每组输入一个整数n（4<=n<=5000），代表凸多边形的边数
输出描述:
对于每组数据输出一个整数，代表n变形不同分法的种数，为了便于输出，输出结果对1e9+7取模