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
1000
Output:
1
Input:
3 2
1000
Output:
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 |