Lucas' Theorem to solve binomial coefficients

I am happy cause only one problem and i will be done solving interviewstreet mathematical problems. After solving the Binomial Coefficients  problem i think i have something useful to share with you.

In this problem you are given two number N and P, where P is a prime number. You are requested to find how many binomial coefficients of n become to 0 after modulo by P.

So the output should be the number of  s (0<=k<=n)  each of which after modulo operation by P is 0.

I hear you saying its an easy problem, but you won't say that after knowing about the input constraints.

Constraints:

n is less than 10⁵⁰⁰.

P is less than 10⁹.

For such large number i will use Java to solve this problem, thanks to the BigInteger Class in java. After doing some search i found that there is a theorem called Lucas' Theorem which is as follows:

Given n, k, and prime p, binomial (n,k) is divisible by p if and only if at least one of  the base p digits of k is larger than the corresponding digit of m (also base p digit).

So to solve this problem we need to find the base P representation of n, and counting how many numbers (R) that have all digits (in base P) less than the corresponding digit in n.

1. We have k is between 0 and n, so we have (n+1) numbers to check with n.

2. Now need to find R.

Now if n in base P is as follows: abc...

Then we need to get all numbers that have:

1. First digit is 0, 1, 2, .... a-1

2. Second digit is 0, 1, 2, .... b-1

3. Third digit is 0, 1, 2, ...., c-1

Obviously R = (a+1)*(b+1)*(c+1).

So we have (n+1) total numbers, subtracting  R, then the result would be n+1-R.