CF167E Wizards and Bets

给定 $n(1 \le n \le 600)$ 个点 $m(0 \le m \le 10^5)$ 条边的有向无环图，其中没有入度的点被视为源点，没有出度的点被视为汇点。保证源点和汇点数目相同。考虑所有把源汇点两两配对，并用两两不相交的路径把它们两两连接起来的所有方案。 如果这个方案中，把源点按标号 $1$ 到 $n(1 \le n \le 600)$ 排序后，得到的对应汇点序列的逆序数对的个数是奇数，那么 A 给 B 一块钱，否则 B 给 A 一块钱。问最后 A 的收益，对质数 $p(2 \le p \le 10^9 + 7)$ 取模。

第一行包含三个整数 $n, m, p(1 \le n \le 600, 0 \le m \le 10^5, 2 \le p \le 10^9 + 7)$。 接下来 $m$ 行每行包含两个整数 $u, v(1 \le u, v \le n)$，表示从顶点 $u$ 到顶点 $v$ 的一条有向边。保证构成的图不循环，且源点的数量等于汇点的数量。

输出 A 玩家的总奖金对 $p$ 取模。请注意，奖金可能是负数但是取模后必须是非负的。

在第一个示例中，正好有一组路径 $(1 \to 3), (2 \to 4)$。反转数为 $0$，即偶数。因此，A 玩家得到 $1$ 枚硬币。 在第二个示例中，正好有一组路径 $(4 \to 1), (3 \to 2)$。正好有一个反转。因此，A 玩家得到 $-1$ 枚硬币。 在第三个示例中，有两组路径，它们以相反的符号计数。 在第四个样本中，没有任何一组路径。 在第五个样本中，有三个源（$2, 3, 5$）和三个汇（$1, 2, 4$）。对于单组路径 $(5 \to 1), (3 \to 4), (2 \to 2)$ 有 $2$ 个反转，即它们的数量是**偶数**。