Awards

Time limit2sMemory limit1024 MB

Summary

Count ways to pick k non-adjacent employees out of n in a row, modulo a prime m, with n up to 100000.

Level: Medium4 of 10
Topics: Math, Combinatorics
Solved: No attempts yet

Problem

A company decides to give awards to $k$ of its $n$ employees. The employees stand in a single row, and each employee sees only the people directly next to them. So that every award winner feels singled out, no two award winners may stand next to each other in the row.

Count the ways to hand out $k$ awards among the $n$ employees in this row, subject to that rule. The count can be very large, so output it modulo the prime $m$ .

Input

The first and only line contains three non-negative integers $n$ , $k$ , and $m$ : the number of employees, the number of awards, and a prime modulus ( $1 \le k \le n \le 100000$ , $1 \le m \le 10^9$ ).

Output

Print the answer modulo $m$ on a single line.

Examples2

Example 1
Input
```
3 2 569
```
Expected output
```
1
```
Example 2
Input
```
5 2 673
```
Expected output
```
6
```