#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int mod =1e9+7;

int n;

int qmi(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=(LL)res*a%mod;
        a=(LL)a*a%mod;
        b>>=1;
    }
    return res;
}

int main()
{
    cin>>n;
    int res=1;
    int a=2*n,b=n;
    for(int i=a;i>b;i--) res=(LL)res*i%mod;//因为mod为质数可以用费马小定理求解，否则只能用扩展欧几里得算法
    int ne=1;
    for(int i=1;i<=b;i++) ne=(LL)ne*i%mod;
    res=(LL)res*qmi(ne,mod-2)%mod;
    res=(LL)res*qmi(n+1,mod-2)%mod;
    cout<<res;
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 5010;
int a,b;

int primes[N],cnt;
int sum[N];
bool st[N];


void get_primes(int n)  // 线性筛质数
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++)
        {
            st[i*primes[j]]=true;
            if(i%primes[j]==0) break;
        }
    }
}

vector<int> mul(vector<int>a,int b)
{
    vector<int>c;
    int t=0;
    int n=a.size();
    for(int i=0;i<n;i++)
    {
        t+=b*a[i];
        c.push_back(t%10);
        t/=10;
    }
    while(t)
    {
        c.push_back(t%10);
        t/=10;
    }
    return c;
}

int get(int a,int p)
{
    int res=0;
    while(a)
    {
        res+=a/p;
        a/=p;
    }
    return res;
}

int main()
{
    cin>>a>>b;
    get_primes(a);

    for(int i=0;i<cnt;i++)
        sum[i]=get(a,primes[i])-get(b,primes[i])-get(a-b,primes[i]);

    vector<int>res;
    res.push_back(1);

    for(int i=0;i<cnt;i++)
        for(int j=0;j<sum[i];j++)
            res=mul(res,primes[i]);

    for(int i=res.size()-1;i>=0;i--) cout<<res[i];
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

int p;

int qmi(int a,int b)
{
    int res=1%p;
    while(b)
    {
        if(b&1) res=(LL)res*a%p;
        a=(LL)a*a%p;
        b>>=1;
    }
    return res;
}

int C(int a,int b)
{
    if(b>a) return 0;
    if(b==a) return 1;

    if(b>a-b) b=a-b;
    int x=1,y=1;
    for(int i=0;i<b;i++)
    {
        x=(LL)x*(a-i)%p;
        y=(LL)y*(i+1)%p;
    }
    return (LL)x*qmi(y,p-2)%p;
}

int lucas(LL a,LL b)
{
    if(a<p&&b<p) return C(a,b);
    else return (LL)C(a%p,b%p)*lucas(a/p,b/p)%p;
}

int main()
{
    int n;
    cin>>n;
    while(n --)
    {
        LL a,b;
        cin>>a>>b>>p;
        cout<<lucas(a,b)<<endl;
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=2010,mod=1e9+7;

int n,a,b;
int g[N][N];

void init()
{
    for(int i=0;i<N;i++)
        for(int j=0;j<=i;j++)
        {
            if(j==0) g[i][j]=1;
            else g[i][j]=(g[i-1][j]+g[i-1][j-1])%mod;
        }
}
int main()
{

    cin>>n;
    init();
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
            cout<<g[i][j]<<' ';
        cout<<endl;
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 1e5+10;
const int mod=1e9+7;
int fact[N],infact[N];

int qmi(int a,int b,int p)
{
    int res=1;
    while(b)
    {
        if(b&1) res=(LL)res*a%p;
        a=(LL)a*a%p;
        b>>=1;
    }
    return res;
}

int main()
{
    fact[0]=infact[0]=1;
    for(int i=1;i<=N;i++)
    {
        fact[i]=(LL)fact[i-1]*i%mod;
        infact[i]=(LL)infact[i-1]*qmi(i,mod-2,mod)%mod;
    }

    int n;
    cin>>n;
    while (n -- )
    {
        int a,b;
        cin>>a>>b;
        printf("%d\n",(LL)fact[a]*infact[b]%mod*infact[a-b]%mod);//加long long因为乘的时候可能会溢出
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    LL d=exgcd(b,a%b,x,y);
    int t=y;
    y=x-a/b*y;
    x=t;
    return d;
}
int main()
{
    int n;
    cin>>n;
    LL a1,m1;
    cin>>a1>>m1;
    bool has_answer=true;
    for(int i=0;i<n-1;i++)
    {
        LL a2,m2;
        cin>>a2>>m2;
        LL k1,k2;
        LL d=exgcd(a1,a2,k1,k2);
        if((m2-m1)%d)
        {
            has_answer=false;
            break;
        }
        k1*=(m2-m1)/d;
        LL t=a2/d;
        k1=(k1%t+t)%t;
        m1=k1*a1+m1;
        a1=abs(a1/d*a2);

    }
    if(!has_answer)
        cout<<-1<<endl;
    else
        cout<<(m1%a1+a1)%a1<<endl;

}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

int exgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,x,y);
    int t=y;
    y=x-a/b*y;
    x=t;
    return d;
}

int main()
{
    int n;
    cin>>n;
    while (n -- )
    {
        int a,b,m;
        cin>>a>>b>>m;
        int x,y;
        int d=exgcd(a,m,x,y);
        if(b%d) cout<<"impossible"<<endl;
        else cout<<(LL)x*(b/d)%m<<endl;
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int exgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,x,y);
    int t=y;
    y=x-a/b*y;
    x=t;
    return d;
}

int main()
{
    int n;
    cin>>n;
    while (n -- )
    {
        int a,b,x,y;
        cin>>a>>b;
        exgcd(a,b,x,y);
        cout<<x<<' '<<y<<endl;
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int exgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

int main()
{
    int n;
    cin>>n;
    while (n -- )
    {
        int a,b,x,y;
        cin>>a>>b;
        exgcd(a,b,x,y);
        cout<<x<<' '<<y<<endl;
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;


int qmi(int a,int k,int p)
{
    int res=1;
    while(k)
    {
        if(k&1)res=(LL)res*a%p;
        a=(LL)a*a%p;
        k>>=1;
    }
    return res;
}

int main()
{
    int n;
    cin>>n;
    while (n -- )
    {
        int a,p;
        cin>>a>>p;
        int res=qmi(a,p-2,p);
        if(a%p==0) cout<<"impossible"<<endl;
        else cout<<res<<endl;
    }
    return 0;
}