Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
111 - ZOJ Monthly, October 2011 - I
How Many Sets II

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Given a set S = {1, 2, ..., n}, number m and p, your job is to count how many set T satisfies the following condition:

  • T is a subset of S
  • |T| = m
  • T does not contain continuous numbers, that is to say x and x+1 can not both in T

Input

There are multiple cases, each contains 3 integers n ( 1 <= n <= 109 ), m ( 0 <= m <= 104, m <= n ) and p ( p is prime, 1 <= p <= 109 ) in one line seperated by a single space, proceed to the end of file.

Output

Output the total number mod p.

Sample Input

5 1 11
5 2 11

Sample Output

5
6

Author: QU, Zhe
Submit    Status