I'm having problems understanding how to solve this problem https://atcoder.jp/contests/abc156/tasks/abc156_d

I've seen a lot of solutions, I've checked almost everything on the internet but nothing helps me because I simply don't understand a single algorithm used in this problem.

I've never used fast exponentiation, extended euclidean algorithm, inverse modulo, lucas theorem or whatever other algorithm I need for this problem before, and I'm having problems understanding what to use, which to use, and how to implement it.

I understand fast exponentiation and I think I can calculate 2^N in this problem, but I don't how to calculate binomial coefficients of N over a and N over b, could anyone help ?

And please understand that I'm really unfamiliar with these kinds of math problems, but I'm starting to learn them, so please make implementation as simple as possible.