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.

Lucas Theorem

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:

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.

Generalize to this Problem

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 .

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.