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

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 |