Eva

Description

有一个正n多边形，我们要连接一些对角线，把这个多边形分成若干个区域。要求连接的对角线不能相交，每个点
可以连出也可以不连出对角线。（即最终不要求所有区域均为三角形）问总方案数mod (10^9+7)的结果。

一行一个整数n,n≤10^6

一行一个整数表示答案。

5

11

/**************************************************************

    Problem: 4706

    User: ictsing

    Language: C++

    Result: Accepted

    Time:2232 ms

    Memory:16912 kb

****************************************************************/

 

#include<iostream>

#include<cstdio>

using namespace std;

typedef long long ll;

const int mod = 1e9+7;

const int mt= 1e6+7;

ll inv[mt],f[mt];

int main()

{

    inv[0]=1,inv[1]=1;

    f[0]=1,f[1]=1;

    int x;

    scanf("%d",&x);

    for(int i=2;i<=x;i++)

        inv[i]=(mod-mod/i)*inv[mod%i]%mod;

    for(int i=2;i<x;i++)

        f[i]=((6*i-3)*f[i-1]%mod-(i-2)*f[i-2]%mod+mod)%mod*inv[i+1]%mod;

    printf("%lld\n",f[x-2]);

}