Bracket Sequences I

1#include<bits/stdc++.h>
2using namespace std;
3#define int unsigned long long
4const int m=1e9+7;
5int binpow(int a,int b){
6  int ret=1;
7  while(b){
8    if(b&1) ret=ret*a%m;
9    a=a*a%m,b>>=1;
10  }
11  return ret;
12}
13signed main(){
14  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
15  int n; cin>>n;
16  if(n&1){  // n is odd <=> no valid bracket sequences
17    cout<<"0\n";
18    return 0;
19  }
20  int ans=1;
21  for(int i=2; i<=(n>>1); ++i){
22    ans = ans * (4*i-2) % m;
23    ans = ans * binpow(i+1,m-2) % m;
24  }
25  cout << ans << '\n';
26  return 0;
27}