Binomial Coefficient 5

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

Medium7Number theoryCombinatoricsNo attempts yetTime limit1sMemory limit256 MB

Description

Examples5

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.