Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<cstdio>
- using namespace std;
- #define max 1000000
- long long a[max+1];
- long long extended_euclid(long long a,long long b){ // ax+by=gcd(a,b) where a>b
- long long x1,x2,y1,y2;
- x1=1;
- y1=0;
- x2=0;
- y2=1;
- long long q;
- long long r;
- long long x_new;
- long long y_new;
- for( ; b>0 ; ){
- q=a/b;
- r=a%b;
- x_new=x1-(q*x2);
- y_new=y1-(q*y2);
- a=b;
- b=r;
- x1=x2;
- y1=y2;
- x2=x_new;
- y2=y_new;
- }
- return y1;
- }
- void cal(){
- a[0]=1;
- a[1]=1;
- long long i;
- long long res=1;
- long long mod=1000000007LL;
- for(i=2;i<=1000000;i++){
- res *= ((4*i)-2);
- res %= mod;
- long long y=extended_euclid(mod,i-1);
- if(y<0)
- y += mod;
- // cout<<y<<" ";
- res *= y;
- res %= mod;
- a[i]=res;
- // cout<<a[i]<<"\n";
- }
- }
- int main()
- {
- cal();
- // cout<<"n\n";
- int t;
- cin>>t;
- long long mod=1000000007LL;
- for(int w=0;w<t;w++){
- long long n;
- cin>>n;
- long long res=a[n];
- cout<<res%mod<<"\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement