## PT07D - Let us count 1 2 3

no tags

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
```

hide comments ymGXX: 2010-03-22 02:34:27 Too strict time limit....

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