NMNMX what's wrong?

The solution is partially accepted.

According to Fermat Little Theorem:-
x^{\binom{a}{b}} mod p = x^{\binom{a}{b} mod \left( p-1 \right) } mod p

and you have done x^{\binom{a}{b} mod \left( p \right) } mod p

you can check my solution as refrence:-https://www.codechef.com/viewsolution/19209235


above line is causing WA because if you check 5500C3000 your array value will be 0 because you computed till 2750.
now to correct you have 2 ways:-

1.) compute till 5500C5500

2.) as \binom{n}{k} = \binom{n}{n-k} you can compute till 2750 but when querying value of binomial coefficients you have to make sure to change k>2750 to n-k.

1 Like

It did help but I am still getting wrong answer in last three test case. With the help of your solution I did my best in optimizing the code. here is the new solution:https:-//www.codechef.com/viewsolution/19271816

1 Like

Thanks for the help bro. It worked :slight_smile: