D. Улики
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Расследуя очередное дело, Шерлок Холмс нашел некоторое количество улик. Также он нашел прямые связи между некоторыми из этих улик. Прямые связи между уликами не направлены. То есть, прямая связь между уликами A и B и прямая связь между уликами B и A — это одно и тоже. Кроме того, между двумя уликами может существовать не более одной прямой связи.

Конечно, Шерлок может найти прямые связи между всеми уликами. Но это займет слишком много времени — преступники могут успеть залечь на дно. Чтобы раскрыть дело, ему надо добиться того, чтобы каждая улика была связана со всеми остальными (возможно, не напрямую). Улики A и B считаются связанными, если есть прямая связь между ними или есть прямая связь между уликой A и некой уликой C, которая связана с B.

Шерлок Холмс посчитал минимальное количество прямых связей между уликами, которые ему еще надо найти, чтобы раскрыть дело. Оно оказалось равно ровно T.

Посчитайте, пожалуйста, количество различных способов найти ровно T прямых связей между уликами так, чтобы дело оказалось раскрытым. Два способа считаются различными, если существует хотя бы одна такая пара улик, что в одном способе между ними найдена прямая связь, а в другом — нет.

Поскольку количество способов может оказаться очень большим, выведите его по модулю k.

Входные данные

В первой строке записаны через пробел три целых числа n, m, k (1 ≤ n ≤ 105, 0 ≤ m ≤ 105, 1 ≤ k ≤ 109) — количество улик, количество прямых связей между уликами, которые уже известны Холмсу, и модуль, по которому необходимо вывести ответ.

В следующих m строках даны по два целых числа a и b (1 ≤ a, b ≤ n, a ≠ b), обозначающие прямую связь между уликами. Гарантируется, что между двумя уликами есть не больше одной прямой связи. Обратите внимание, что прямые связи между уликами не направлены.

Выходные данные

Выведите единственное целое число — ответ на задачу по модулю k.

Примеры
Входные данные
2 0 1000000000
Выходные данные
1
Входные данные
3 0 100
Выходные данные
3
Входные данные
4 1 1000000000
1 4
Выходные данные
8
Примечание

В первом примере есть всего две улики, и Шерлок пока не нашел между ними прямой связи. Есть единственный способ раскрыть дело — найти эту связь.

Во втором примере есть три улики, И Шерлок пока не нашел никаких прямых связей между ними. Ему нужно найти две из трех возможных прямых связей между уликами, чтобы раскрыть дело — есть 3 способа это сделать.

В третьем примере четыре улики, и уже найдена одна прямая связь, между первой и четвертой уликами. Есть 8 способов найти еще две прямых связи так, чтобы дело было раскрыто.