Again ICL2015Finals : Problem on Number Theory

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	170
2	maomao90	162
2	Um_nik	162
4	atcoder_official	160
5	djm03178	158
5	-is-this-fft-	158
7	adamant	154
7	Dominater069	154
9	awoo	153
10	luogu_official	152

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.