Given 3 integers n, r and m. You task is to calculate ^{n}Cr%m.
Note: m is a square free number and largest prime factor of m <= 50.

Example 1:
Input: n = 5, r = 2, m = 98697
Output: 10
Explanation: ^{5}C2 = 5!/(2!3!) = 10%98697 = 10
Example 2:
Input: n = 3, r = 2, m = 98697
Output: 3
Explanation: ^{3}C2 = 3!/(2!1!) = 3%98697 = 3

Your Task:
You don't need to read or print anything. Your task is to complete the function nCrModM() which takes n, r and m as input parameter and returns nCr modulo m.

Expected Time Complexity: O(m + log_{m}n)
Expected Space Complexity: O(m)

Constraints:
1 <= r <= n <= 10^{9}
1 <= m <= 10^{5}

见题面

见题面