Friday, 25 September 2015

ncr using inverse modulo

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define ll long long int
#define mod 1000000007

ll powmod(ll a,ll b)
    {
    b=mod-2;
    ll result=1;
    while(b)
        {
        if(b&1)
            result=(result*a)%mod;
        b=b>>1;
        a=(a*a)%mod;
    }
    return result;
}
int main() {

    int t,n,m,i;
    ll fact[201];
    fact[0]=fact[1]=1;
    for(i=2;i<201;i++)
        fact[i]=(fact[i-1]*i)%mod;
    scanf("%i",&t);
    while(t--)
        {
        scanf("%i%i",&n,&m);
        ll ans=fact[n]*powmod((fact[m],mod);
        printf("%lli\n",ans%mod);
    }
    return 0;
}

No comments:

Post a Comment