Header Extras

// struct pair

typedef struct mmm
{
   int a,b;
}pai;


//  (a^b)%c
lld mod_power(lld a, lld n, lld mod){

    // returns (a^n) % mod.
    // '%' represents modulus operation.

    lld y = 1;
    while(n){
        if(n & 1)
            y = (y * a) % mod;
        a = (a * a) % mod;
        n >>= 1;
    }
    return y;
}

//  inverse modulo

lld inverse(lld num){

    // returns the inverse of num w.r.t. (10^9 + 7).
    // uses the property a^(-1) mod p = a^(p-2) mod p.
    return mod_power(num, MOD - 2, MOD);
}

 sieve
bool p[10000000000];
int prime(int a)
{
   for(int i=2;i*i<=a;i++)
   {
       if(!p[i])
       for(int j=2;i*j<=a;j++)
           p[i*j]=1;
   }
}