Python3 solution

# Enter your code here. Read input from STDIN. Print output to STDOUT
import sys

def go():
    n, k, p = map(int, sys.stdin.readline().split())
    A = n + 1
    B = k + 1
    res = 1
    f = [1]
    for i in range(1, p):
        f.append(f[-1] * i % p)
    while A or B:
        a, b = A % p, B % p
        A //= p 
        B //= p
        if a < b: return 0
        res *= f[a] * pow(f[b] * f[a-b] % p, p - 2, p)
        res %= p
    return res

for _ in range(int(sys.stdin.readline())):
    print(go())

C++ CODE .............. I TRIED AND SUCEED

include

using namespace std;

define MAXP 100000

int p; long long fact[MAXP];

long long get_exp(long long n){ long long ret = 0;

while(n){
    n /= p;
    ret += n;
}

return ret;

}

int calc(long long n){ if(n == 0) return 1;

int ret = calc(n / p) * fact[n % p] % p;

if((n / p) & 1)
    ret = p - ret;

return ret;

}

long long mod_pow(long long a, int b){ long long ret = 1;

while(b){
    if(b & 1) ret = ret * a % p;
    a = a * a % p;
    b >>= 1;
}

return ret;

}

long long comb(long long n, long long m){ if(get_exp(n) > get_exp(m) + get_exp(n - m)) return 0;

return calc(n) * mod_pow((long long)calc(m) * calc(n - m) % p,p - 2) % p;

}

int main(){ int T;

scanf("%d",&T);

long long N,K;

while(T--){
    scanf("%lld %lld %d",&N,&K,&p);

    fact[0] = 1;

    for(int i = 1;i < MAXP;++i){
        int aux = i;

        while(aux % p == 0)
            aux /= p;

        fact[i] = fact[i - 1] * aux % p;
    }

    printf("%lld\n",comb(N + 1,K + 1));
}

return 0;

}

My answer seems to be working right for most of the test cases, but got wrong on nearly half of the tests. I cannot think of any reason why that happens. Based on the editorial the calculation should be very straight forward. Can you guys look at the output and give me some hint where I got it wrong?

I calculate nCr mod P directly by cancelling out the small prime factors in the anominator and denominator of N!/(K!*(N-K)!). It's much more efficient than the way proposed by the editorial. But I still cannot get it right.

Any hint on how can I reduce the time taken for execution? I am using BigInteger, and it's working well until and unless there isn't any time limit.

In the editorial, I am unable to understant the part where inverse of n is being calculated.

Precisely, this part =>

calculate inverses mod p

for i in xrange(2,p): inv[i] = (p - p/i) * inv[p%i] % p

I know how to calculate inverse using extended Euler's theorem. It would be nice if you could elaborate the logic behind it or share some link.