시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 1024 MB | 84 | 38 | 16 | 27.119% |
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.
9 2 3
1
5 2 5
2
6 3 6
2
7654321 1234567 1050
210