//ABC003-D nCr logN #include #include #include #define inf 1072114514 #define llinf 4154118101919364364 #define mod 1000000007 int max(int a,int b){if(a>b){return a;}return b;} int min(int a,int b){if(a= b){return (a/b)+1;}return a/b;} int ceil(int a,int b){if(a%b==0){return a/b;}return (a/b)+1;} int gcd(int a,int b){int c;while(b!=0){c=a%b;a=b;b=c;}return a;} int lcm(int a,int b){int c=gcd(a,b);a/=c;return a*b;} int nCr(int a,int b){int i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;} int fact(int a){int i,r=1;for(i=1;i<=a;i++){r*=i;}return r;} int pow(int a,int b){int i,r=1;for(i=1;i<=b;i++){r*=a;}return r;} long long llmax(long long a,long long b){if(a>b){return a;}return b;} long long llmin(long long a,long long b){if(a= b){return (a/b)+1;}return a/b;} long long llceil(long long a,long long b){if(a%b==0){return a/b;}return (a/b)+1;} long long llgcd(long long a,long long b){long long c;while(b!=0){c=a%b;a=b;b=c;}return a;} long long lllcm(long long a,long long b){long long c=llgcd(a,b);a/=c;return a*b;} long long llnCr(long long a,long long b){long long i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;} long long llfact(long long a){long long i,r=1;for(i=1;i<=a;i++){r*=i;}return r;} long long llpow(long long a,long long b){long long i,r=1;for(i=1;i<=b;i++){r*=a;}return r;} double dbmax(double a,double b){if(a>b){return a;}return b;} double dbmin(double a,double b){if(a*(int *)b){return 1;}if(*(int *)a==*(int *)b){return 0;}return -1;} int sortfnckj(const void *a,const void *b){if(*(int *)a<*(int *)b){return 1;}if(*(int *)a==*(int *)b){return 0;}return -1;} int llsortfncsj(const void *a,const void *b){if(*(long long *)a>*(long long *)b){return 1;}if(*(long long *)a==*(long long *)b){return 0;}return -1;} int llsortfnckj(const void *a,const void *b){if(*(long long *)a<*(long long *)b){return 1;}if(*(long long *)a==*(long long *)b){return 0;}return -1;} int dbsortfncsj(const void *a,const void *b){if(*(double *)a>*(double *)b){return 1;}if(*(double *)a==*(double *)b){return 0;}return -1;} int dbsortfnckj(const void *a,const void *b){if(*(double *)a<*(double *)b){return 1;}if(*(double *)a==*(double *)b){return 0;}return -1;} long long power(long long a,long long b){ long long x=1,y=a; while(b>0){ if(b&1ll){ x=(x*y)%mod; } y=(y*y)%mod; b>>=1; } return x%mod; } long long modular_inverse(long long n){ return power(n,mod-2); } long long factorial[524288]; long long invfact[524288]; void cfact(){ long long i; factorial[0]=1; factorial[1]=1; for(i=2;i<524288;i++){ factorial[i]=factorial[i-1]*i; factorial[i]%=mod; } invfact[524287]=modular_inverse(factorial[524287]); for(i=524286;i>=0;i--){ invfact[i]=invfact[i+1]*(i+1); invfact[i]%=mod; } } long long calcnCr(long long n,long long k){ if(k<0 || n