#P1375. 小猫

小猫

题目描述

2n2n 只小猫站成一圈,主人小明想把它们两两之间用绳子绑住尾巴连在一起。同时小明是个完美主义者,不容许看到有两根绳子交叉。请问小明有几种连线方案,可以把让所有小猫两两配对?

方案数很大,仅需输出方案数模 109+710^9+7(一个质数)的值。

输入格式

输入共一行,一个整数 nn

输出格式

输出方案数对 109+710^9+7 取模后的值。

3
5

提示

数据范围

  • 对于 60%60\% 的数据,1N1001\le N \le 100
  • 对于 100%100\% 的数据,1N1051\le N \le 10^5