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 <= 109.
For Kind 3 or Kind 4 query, 1 <= n <= 103 and n <= p.
For all queries, 2 <= p <= 104 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

Added by:Thanh-Vy Hua
Date:2007-04-07
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Co-author Amber

hide comments
2022-02-23 10:10:47
there's something wrong with the data, I found n>p for kind 3 or 4
2010-03-22 02:34:27 ymGXX
Too strict time limit....
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.