11016: NC21507 - 吴老板教课
[Creator : ]
Description
无所不能的吴老板经常教导他学生，学数学要临场快速突击：
那么现在吴老板给大家一个数论公式
令 $h(0)=1,h(1)=1$，
卡特兰数满足递推式 ：
$h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)*h(0)\ (n\ge 2)$
通项公式可以写成：
$h(n)= C(n, 2n) - C(n +1, 2n)$ (C是组合数符号）
吴老板给大家的任务很简单，结合以上公式，求出第 $1$ 项到第 $n$ 项的卡特兰数的和（结果对 $100,000,007$ 取模）
Input
输入一个整数 $n\ (2 \leq n \leq 100,000)$
Output
输出一个整数代表前 $n$ 个卡特兰数的和
Sample 1 Input
3
Sample 1 Output
8
1+2+5=8