시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 1024 MB 0 0 0 0.000%

문제

Modulo (mod) is a very common operator on integers. For two integers n and d with d > 0, r ≡ (n mod d) is defined where 0 ≤ r < d and there exists an integer q, such that n = q × d+r. For example, (200 mod 5) ≡ 0 means that the remainder of 200 divided by 5 is 0. Here is another new operator called DivModulo (dmod) defined as follows. For two integers n and d with d > 0, r ≡ (n dmod d) is defined where there exists two integers m and h, such that r ≡ (m mod d), n = m × dh, and d is not a factor of m. For example, (200 dmod 5) ≡ 3, since (200 dmod 5) ≡ (8 × 52 dmod 5) ≡ (8 mod 5) ≡ 3.

Consider the factorials and the combination function. For an integer M ≥ 0, the factorial M! is defined as M! = M × (M −1) × (M −2) × · · · × 3 × 2 × 1, and 0! = 1 is defined. For integers M and N with 0 ≤ N ≤ M, the combination function C(M, N) is defined as C(M, N) = M!/(N!×(M−N)!). Now given three integers M, N, D with D > 0, please compute C(M, N) dmod D. For example, (C(9, 2) dmod 3) ≡ (36 dmod 3) ≡ (4 × 32 dmod 3) ≡ (4 mod 3) ≡ 1.

입력

Three integers M, N and D are given in one line.

출력

Please output C(M, N) dmod D in one line.

제한

  • 1 ≤ M ≤ 4 × 1018
  • 0 ≤ N ≤ M
  • 2 ≤ D ≤ 1.6 × 107

예제 입력 1

9 2 3

예제 출력 1

1

예제 입력 2

5 2 5

예제 출력 2

2

예제 입력 3

6 3 6

예제 출력 3

2

예제 입력 4

7654321 1234567 1050

예제 출력 4

210