在 Byteotia 有两棵极高的树，每棵树的树干上都凿有许多树洞，一个挨着一个。很久以前，一些飞得很快的鸟决定住进这些树洞里。其中一些鸟彼此认识，因此它们希望能够互相拜访对方的树洞。鸟儿们飞行速度极快，且总是沿直线飞行。为了避免碰撞的危险，它们决定按照以下方式分配树洞：

• 每一对想要互相拜访的鸟必须住在不同的树上，并且
• 对于任意两对相互认识的鸟，连接这两对鸟所在树洞的线段不能相交（但它们可以拥有共同的端点）。

此外，鸟儿们希望尽可能住在低处。因此，在每棵树上，它们都占据了一定数量的较低的树洞。每棵树上的树洞数量都多于鸟的总数。

众所周知，鸟的脑容量很小。这就是为什么它们请求你——一位受人尊敬的鸟类学家——帮助它们找出有多少种分配树洞的方法。

编写一个程序：

• 从标准输入读取鸟类之间相互认识的关系，
• 计算满足上述约束条件的鸟类分配方案总数，
• 将结果写入标准输出。

输入格式

标准输入的第一行包含三个整数 $n$、$m$ 和 $k$，分别表示：鸟的数量、相互认识的鸟的对数以及计算结果时需要取模的数（详见输出格式），$2 \le n \le 1\,000\,000$，$1 \le m \le 10\,000\,000$，$2 \le k \le 2\,000\,000$。鸟的编号从 $1$ 到 $n$。接下来的 $m$ 行给出了相互认识的鸟的对，每行一对。第 $i+1$ 行包含两个由空格分隔的整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$，$a_i \neq b_i$）。这些是相互认识的鸟的编号。每一对（无序）相互认识的鸟只会出现一次。

输出格式

设 $r$ 为满足给定约束条件的鸟类分配方案总数。你的程序应在标准输出的第一行输出一个整数：$r$ 除以 $k$ 的余数。如果不存在合法的分配方案，则结果为 $0$。

样例

输入 1

3 2 10
1 2
1 3

输出 1

4