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