在一些国家生活着巫师。他们喜欢下奇怪的赌注。
两个向导绘制了一个具有 n 个顶点和 m 个边的无环有向图(该图的顶点编号从 1 到 n)。源是没有传入边的顶点,汇是没有传出边的顶点。请注意,一个顶点可以同时是汇点和源点。在向导图中,接收器和源的数量是相同的。
Wizards 按照顶点数从 1 到 k 递增的顺序对源进行编号。汇点以类似的方式从 1 到 k 进行编号。
为了打赌,他们像真正的巫师一样施展咒语,选择一组从所有源到汇的 k 条路径,使得没有两条路径在顶点相交。在这种情况下,每个接收器都有一条从同一个源到它的路径。假设第 i 个接收器有一条从 ai 源到它的路径。然后,如果 i < j 且 ai > aj,则称对 (i, j) 为反转。如果所有可能对 (i, j) 之间的反转次数(即 (1 ≤ i < j ≤ k))为偶数,则第一个巫师获胜(第二个巫师给他一枚魔法硬币)。否则,第二个巫师获胜(他从第一个巫师那里得到一枚魔法硬币)。
我们的巫师被狂热的兴奋所俘获,所以他们一次又一次地选择新的路径,直到最终他们只选择了每组可能的路径一次。当且仅当存在一条边,该边位于一组中的某个路径且不位于另一组的任何路径上时,两组不相交的路径才被认为是不同的。为了检查他们的笔记,他们要求你计算第一个玩家在所有可能的路径集上以素数 p 为模的总奖金。
输入
第一行包含三个空格分隔的整数 n、m、p (1 ≤ n ≤ 600, 0 ≤ m ≤ 105, 2 ≤ p ≤ 109 + 7)。保证p是素数。
接下来的 m 行包含图形的边缘。每行包含一对空格分隔的整数 ai bi — 从顶点 ai 到顶点 bi 的一条边。保证图是非循环的,并且图包含相同数量的源和汇。请注意,该图可以有多个边。
输出
打印问题的答案 — 第一个玩家的总奖金以素数 p 为模。请注意,奖金可能为负,但模余数必须为非负(参见示例)。
示例
输入 #1
4 2 1000003 1 3 2 4
输出 #1
1
输入 #2
4 2 1000003 4 1 3 2
输出 #2
1000002
输入 #3
4 4 1000003 2 1 2 4 3 1 3 4
输出 #3
0
输入#4
6 5 1000003 1 4 1 5 1 6 2 6 3 6
输出#4
0
输入 #5
5 2 1000003 5 1 3 4
输出 #5
1
注意
在第一个示例中,只有一组路径 — $$(1\rightarrow3),(2\rightarrow4)$$。反转次数为0,为偶数。因此,第一个巫师获得 1 个硬币。
在第二个示例中,只有一组路径 — $$(4\rightarrow1),(3\rightarrow2)$$。恰好有一个反转。因此,第一个巫师获得-1枚硬币。 $$-1 \bmod (10^6 + 3) = 10^6 + 2$$。
在第三个样本中,有两组路径,它们的符号相反。
在第四个示例中根本没有路径集。
在第五个示例中,有三个源 - 带有数字 (2, 3, 5) 的顶点和三个接收器 - 带有数字 (1, 2, 4) 的顶点。对于一组路径 $$(5\rightarrow1),(3\rightarrow4),(2\rightarrow2)$$ 是 2 个反转,即它们的数量是偶数。