PT07D  Let us count 1 2 3
Given two integer n, p. 4 kinds of query is needed to solve:
1. Counting the number of labeled unrooted trees with n nodes
2. Counting the number of labeled rooted trees with n nodes
3. Counting the number of unlabeled rooted trees with n nodes
4. Counting the number of unlabeled unrooted trees with n nodes
Calculate the answer modulo p.
Input
Each line contains three integers k, n, p. k denotes which kind of query this
case is.
For Kind 1 or Kind 2 query, 1 <= n <= 10^{9}.
For Kind 3 or Kind 4 query, 1 <= n <= 10^{3} and n <= p.
For all queries, 2 <= p <= 10^{4} and p is a prime.
Output
For each query, output a line which contains only one integer.
Example
Input: 1 2 2 2 2 3 3 2 5 4 2 3 Output: 1 2 1 1
hide comments
wangrx:
20220223 10:10:47
there's something wrong with the data, I found n>p for kind 3 or 4 

ymGXX:
20100322 02:34:27
Too strict time limit.... 
Added by:  ThanhVy Hua 
Date:  20070407 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Coauthor Amber 