402058: GYM100637 D Ceizenpok’s formula

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. Ceizenpok’s formulatime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Dr. Ceizenp'ok from planet i1c5l became famous across the whole Universe thanks to his recent discovery — the Ceizenpok’s formula. This formula has only three arguments: n, k and m, and its value is a number of k-combinations of a set of n modulo m.

While the whole Universe is trying to guess what the formula is useful for, we need to automate its calculation.

Input

Single line contains three integers n, k, m, separated with spaces (1 ≤ n ≤ 1018, 0 ≤ k ≤ n, 2 ≤ m ≤ 1 000 000).

Output

Write the formula value for given arguments n, k, m.

ExamplesInput
2 1 3
Output
2
Input
4 2 5
Output
1

加入题单

上一题 下一题 算法标签: