The problem can be found here. The statement of this problem is extremely simple, in short, you need to calculate the where M is 142857.

If 142857 is a prime number, then we can just use the Lucas theorem to solve it. However, , that is why the problem is marked as an expert level problem in hackerrank.

The core idea of using Lucas theorem to calculate where P is a prime number is to represent as where a is relative prime to P. To calculate the representation of , we can group of P elements each, so it can be expressed as , so that is relative prime to P, and each group mod P is of the same result.

And then use Wilson theorem which said that . We can finally get the solution to calculate . The python code as follow:

```
def fact_mod(n, p, facts):
"""
Type :: (Int, Int, [Int]) -> (Int, Int)
Suppose n! = a * p^e (mod p), then the function return (a mod p, e)
facts is i!(mod p) for 0 <= i < p, use Lucas theory
>>> facts = gen_fact_mod_prime(7)
>>> fact_mod(5, 7, facts)
(1, 0)
>>> fact_mod(15, 7, facts)
(2, 2)
"""
if (n == 0): return (1, 0)
(a, e) = fact_mod(n // p, p, facts)
e += n // p
if (n // p % 2 != 0): return (a * (p - facts[n % p]) % p, e)
return (a * facts[n % p] % p, e)
```

Notice the tricky in the last two line of the above code. Since , so if the number of group is even, then the result is just
`facts[n % p] % p`

, otherwise is `-facts[n % p] % p`

, which is equivelent to
`(p - facts[n % p]) % p`

.

And then we can express ,
calculate , and
. Then if , must be zero mod P, otherwise, the result should be ```
a1 * modinv
(a2 * a3, P)
```

where `modinv`

is the modulo inverse function.

```
def comb_mod(n, k, p):
"""
Type :: (Int, Int, Int) -> Int
Return C(n, k) mod p, p is a prime number.
>>> comb_mod(5, 3, 7)
3
>>> comb_mod(6, 2, 7)
1
"""
if n < 0 or k < 0 or n < k: return 0
facts = gen_fact_mod_prime(p)
a1, e1 = fact_mod(n, p, facts)
a2, e2 = fact_mod(k, p, facts)
a3, e3 = fact_mod(n - k, p, facts)
if (e1 > e2 + e3):
return 0
else:
return a1 * modinv(a2 * a3 % p, p) % p
```

We can use very similar idea to calculate for . Let , then we need to calculate largest divisors of relative prime to .

This time we group into group each has
items. We first pre calculate the array `facts[0..P^a]`

, `facts[i]`

is the
largest divisors of relative prime to mod . Then
we can use the same strategy when calculate .

```
def comb_mod2(n, r, m, pa, facts1):
"""
Type :: (Int, Int, Int) -> Int
m is of form p^a, and n is very large
"""
p, a = pa
def n_fact_fact(n):
if n is 0 or n is 1:
return 1
elif n < m:
return facts1[n] * n_fact_fact(n // p) % m
else:
a = facts1[m - 1]
b = facts1[n % m]
c = n_fact_fact(n // p)
# print 'n = %d a = %d b = %d c = %d' % (n, a, b, c)
return pow(a, n // m, m) * b * c % m
def get_power(n, p):
ret = 0
while n > 0:
ret += n // p
n //= p
return ret
b = get_power(n, p) - get_power(r, p) - get_power(n - r, p)
if b >= a: return 0
m1 = n_fact_fact(n)
m2 = n_fact_fact(r)
m3 = n_fact_fact(n - r)
return (p ** b) * m1 * modinv_table[(m2, m)] * modinv_table[(m3, m)] % m
```

The above code is just to calculate . The
function `n_fact_fact`

is just to calculate the largest divisor of
mod which is relative to . And `get_power`

is to get the
largest number of b such that .

Finally, we can use Chinese Remainder Theorem to solve the problem. Since , we can calculate , , and , and the modulo numbers are relative prime to each other, so we can use it to finally get the answer.

You can find the whole solution in C++ and Python here.

m00nlight 11 April 2015