Woodpeckers

Two very large trees in Hoengseong, Gangwon-do face each other, and each trunk has sufficiently many holes at different heights. Each of the N woodpeckers must live in exactly one hole, and each hole can contain at most one woodpecker. Some pairs of woodpeckers visit each other's homes. Each such trip follows the straight line segment between the two homes.

To avoid collisions, assign homes so that all of the following conditions hold.

1. Two woodpeckers that visit each other must live in different trees.
2. The line segments connecting the homes of visiting pairs must not cross. Two segments may share an endpoint when they share the same home.

Because the woodpeckers prefer lower holes, the woodpeckers assigned to each tree are considered to occupy the lowest holes of that tree with no gaps. Count the number of valid home assignments.

The first line contains three space-separated integers: the number of woodpeckers N (1 <= N <= 1,000,000), the number of visiting pairs M (1 <= M <= 10,000,000), and the divisor K (1 <= K <= 2,000,000).

The woodpeckers are numbered from 1 to N. Each of the next M lines contains two space-separated woodpecker numbers that form a visiting pair.

Let R be the number of valid home assignments. Print the remainder when R is divided by K. If no valid assignment exists, print 0.

There are no additional hints.