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⁹.
For Kind 3 or Kind 4 query, 1 <= n <= 10³ and n <= p.
For all queries, 2 <= p <= 10⁴ 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