Background

Description

There are two very tall trees in Byteotia, and many hollows have been carved into their trunks at different heights. Now $n$ very fast birds have decided to live in these hollows. Some birds know each other, so they want to visit the birds they know. The birds fly very fast, and they usually fly in straight lines. To avoid colliding in flight, they decide to choose a way to live that satisfies the following condition:

• Every bird can visit each bird it knows, and the visiting routes do not intersect with the visiting routes of other birds (they may share endpoints).

In addition, we want each bird to live as low as possible in height, and it is guaranteed that there are more hollows than birds.

We all know that birds have small brains, so they ask you to count how many ways satisfy the above conditions and output the answer modulo $k$.

Output Format

Let $r$ be the number of different arrangements of the birds that satisfy the given constraints. Your program should print a single integer $r \bmod k$ on the first line of the standard output. If there is no valid arrangement, the correct output is $0$.

3 2 10
1 2
1 3

4

Hint

Translated by ChatGPT 5