#P100088. 原题

原题

题目背景

这是一道原题~~~

题目描述

已知有一个圆,圆上有 nn 个点,用这些点之间不相交的弦将圆分割成若干个区域,请问有多少种分法?

输入格式

输入一个数 nn,表示有 nn 个点。

输出格式

输出可行的方案数,由于答案可能很大,请输出答案 mod109+7\mod 10^{9} + 7 之后的数

样例

1
1

提示

对于 40%40 \% 的数据 1n1031 \leq n \leq 10^3

对于 100%100 \% 的数据 1n1071 \leq n \leq 10^7