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