mod functions.txt

int bigmod(int a, int b)
{
    int ans =1;
    while(b>0)
    {
        if(b&1)
        {
            ans = (ans*1ll*a)%mod;
        }
        a= (a*1ll*a)%mod;
        b>>=1;
    }
    return ans;
}
 
inline int add(int x, int y)
{
    return (x+y>=mod ? x+y-mod : x+y);
}
 
inline int sub(int x, int y)
{
    return (x-y<0 ? x-y+mod : x-y);
}
 
inline int gun(int x, int y)
{
    return ((x*1ll*y)%mod);
}
 
inline int vag(int x, int y)
{
    return (x*1ll* bigmod(y,mod - 2))%mod;
}

int fact[N];
int invfact[N];
void init()
{
    fact[0]=1;
    invfact[0] = 1;
    for(int i=1; i<N; i++){
        fact[i]= gun(fact[i-1],i);
        invfact[i] = bigmod(fact[i] , mod-2);
    }
}
int getncr(int n, int r)
{
    if(n<r || n<0 || r<0)
    {
        return 0;
    }
    return gun(fact[n] , gun(invfact[r] , invfact[n-r]));
}
 
int fun(int n, int r)
{
    assert(n>=r);
    int ans = gun(fact[n] , invfact[n-r]);
    return ans;
}