Apple Distribution

In this problem, you are given n distinct apples collected in an orchard and k baskets provided by the orchard owner. The task is to place all the apples into the baskets such that no basket is empty. Since the apples are all distinct, the number of ways to distribute the apples is given by the number of surjections from an n-element set to a k-element set. Using the principle of inclusion‐exclusion, the formula is:

\(\displaystyle \text{ways} = \sum_{i=0}^{k} (-1)^i \binom{k}{i} (k-i)^n\)

Because the number of ways can be extremely large, you are required to output the answer modulo p.

Input Constraint: The input consists of three integers n, k and p, where 1 ≤ k ≤ n. You may assume that the computation can be completed within 1 second.

inputFormat

The input is a single line containing three space-separated integers: n (the number of apples), k (the number of baskets), and p (the modulus).

outputFormat

Output a single integer: the number of ways to distribute the apples into the baskets (with no basket empty) modulo p.

sample

3 2 1000

6