Utils

// GCD aka HCF
int gcd(int a, int b){
    if(a < b) return gcd(b,a);

    if(b == 0) return a;

    return gcd(b, a%b);
}


// N-choose-R
int NCR(int N, int R){
    int ans = 1;

    R = min(R, N-R);

    for(int r=1, n=N; r<=R; r++, n--){
        int g = gcd(ans,r);
        ans /= g;
        ans *= n;
        ans /= (r/g);
    }

    return ans;
}