딱따구리

강원도 횡성의 두 큰 나무가 서로 마주 보고 있고, 각 나무 기둥에는 높이가 서로 다른 구멍이 충분히 많이 있다. N마리의 딱따구리는 각각 하나의 구멍에서만 살 수 있으며, 한 구멍에는 한 마리만 들어갈 수 있다. 일부 딱따구리 쌍은 서로의 집을 오간다. 이 이동은 항상 두 집을 잇는 직선 선분이다.

충돌을 피하기 위해 다음 조건을 모두 만족하도록 집을 정하려고 한다.

1. 서로 오가는 두 딱따구리는 서로 다른 나무에 살아야 한다.
2. 서로 오가는 쌍들의 집을 잇는 선분들은 서로 교차하면 안 된다. 단, 두 선분이 같은 집을 끝점으로 공유하는 것은 허용된다.

딱따구리들은 가능한 낮은 구멍을 원하므로, 각 나무에 배정된 딱따구리들은 그 나무의 가장 낮은 구멍들부터 빈칸 없이 차지한다고 본다. 조건을 만족하는 집 배정의 수를 구하라.

첫째 줄에 딱따구리의 수 N(1 <= N <= 1,000,000), 서로 오가는 딱따구리 쌍의 수 M(1 <= M <= 10,000,000), 답을 나눌 제수 K(1 <= K <= 2,000,000)가 공백으로 구분되어 주어진다.

딱따구리는 1번부터 N번까지 번호가 붙어 있다. 다음 M개의 줄에는 서로 오가는 두 딱따구리의 번호가 공백으로 구분되어 주어진다.

조건을 만족하는 집 배정의 수를 R이라고 할 때, R을 K로 나눈 나머지를 출력한다. 집을 배정할 수 없으면 0을 출력한다.

추가 힌트는 없다.