Given 2 integers n and r. You task is to calculate ^{n}Cr%1000003.

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

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

Expected Time Complexity: O(m * log_{m}n) where m = 1000003
Expected Space Complexity: O(m)

Constraints:
1 <= n <= r <= 10^{16}

见题面

见题面