## PRETTY - Pretty Functions

Let S = {1, 2, 3, ..., N}.

For a given positive integer K, the function f : S --> S is called "pretty" if, for every X in S, it holds that

f ( f ( f ( ... f ( X ) ... ) ) ) = X, where f is repeated exactly K times.

How many pretty functions are there, modulo M?

### Input

Three natural numbers N, K and M. It holds that 1 <= K <= N <= 30 000 and M <= 10^9.

### Output

Number of pretty functions modulo M.

### Example

Input:

2 1

1000Output:

1

Input:

3 2

1000Output:

4

Explanation of the example input 2: there are four pretty functions, namely:

a) f(1) = 1, f(2) = 2, f(3) = 3;

b) f(1) = 2, f(2) = 1, f(3) = 3;

c) f(1) = 3, f(2) = 2, f(3) = 1;

d) f(1) = 1, f(2) = 3, f(3) = 2.

Added by: | Ivan Katanic |

Date: | 2009-10-26 |

Time limit: | 5s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ASM64 NODEJS PERL6 |

Resource: | author: Adrian Satja Kurdija |