Again ICL2015Finals : Problem on Number Theory

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

So again I am writing a post about ICL2015 Finals. My last post was about a DP problem which was not that much hard. But now I am really stuck by a tough problem (I am mentioning this one as tough because number of people who solved it was really low).

What I did for this one? Well, whatever I did to solve this problem was based on this tutorial from CodeChef. You can check that out.

In short the problem is:

Given n,k,m where n,k<=10^18, m<=10^6, we need to find C(n,k)%m where C(n,k) means number of ways to choose k objects from n objects.

So, the question is: What did I do to solve this problem?

Following the tutorial, I prime factorized m. Eventually, I got some prime numbers as factors. Then I applied Lucas' Theorem for each of this prime. After calculating answers for each of this prime, I had to solve some equations of the form X = A[i] (mod M[i]).

And these equations can be solved by Chinese Remainder Theorem.

Now, where did I get stuck? I did all these things mentioned above. But when we are given an m when m has prime powers in its factorized form, I could not find a solution to calculate the required result.

Let me give a quick example.

Imagine, n=10, k=5, m=12341. To find X=C(10,5)%12341, I first prime factorized 12341. So 12341=7*41*43.

I applied Lucas' Theorem for each of the prime factors. What I got is:

X = 0 (mod 7);
X = 6 (mod 41);
X = 37 (mod 43);

Now my task was to combine this equations to find our X. I applied CRT for this and got the required answer 252. Yahooo! :D

But wait, when m=1000 (or some number with prime powers), it didn't work. :(

This is where I need a solution. I actually need to calculate C(n,r)%m where m is of the form p^a where p is a prime.

As you can realize, I am not quite good. It will be too much helpful if you share your ideas on how to solve the above mentioned problem and give instructions to code it in detail, step by step. And I will be really grateful to you. :)

PS1: I found few ideas on how to get around this problem online. But I could not understand and of course could not code anything.

PS2: Really sorry for the long post.