吴老板教课
题号：NC21507
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

无所不能的吴老板经常教导他学生，学数学要临场快速突击：
那么现在吴老板给大家一个数论公式
令h(0)=1,h(1)=1，
卡特兰数满足递推式 ：
h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)*h(0) (n>=2)
通项公式可以写成：
h(n)= C(n, 2n) - C(n +1, 2n) (C是组合数符号）
吴老板给大家的任务很简单，结合以上公式，求出第1项到第n项的卡特兰数的和（结果对100000007取模）

输入描述:

输入一个整数n

输出描述:

输出一个整数代表前n个卡特兰数的和
示例1

输入

复制 
3

输出

复制 
8

说明

1+2+5=8

备注:

2<=n<=100000

（注意：如你不会逆元，那你就需要自己推出卡特兰数另一个递推公式了）