Binomial Coefficient 5

Time limit1sMemory limit256 MB

Summary

Compute the remainder of the binomial coefficient C(N, K) divided by M, where M is not necessarily prime.

Level: Medium7 of 10
Topics: Number theory, Combinatorics
Solved: No attempts yet

Problem

You are given a natural number $N$ and an integer $K$ . Write a program that computes the remainder of the binomial coefficient $\binom{N}{K}$ divided by $M$ . $M$ is not guaranteed to be prime.

Input

The first line contains $N$ , $K$ , and $M$ , separated by spaces. ( $1 \le N \le 4 \times 10^6$ , $0 \le K \le N$ , $2 \le M \le 4 \times 10^6$ )

Output

Print the remainder of $\binom{N}{K}$ divided by $M$ on the first line.

Examples5

Example 1
Input
```
5 2 3
```
Expected output
```
1
```
Example 2
Input
```
30 3 3
```
Expected output
```
1
```
Example 3
Input
```
100 45 13
```
Expected output
```
2
```
Example 4
Input
```
100 46 72
```
Expected output
```
48
```
Example 5
Input
```
50 23 9
```
Expected output
```
1
```