CF167E.Wizards and Bets

In some country live wizards. They like to make weird bets.

Two wizards draw an acyclic directed graph with n vertices and m edges (the graph's vertices are numbered from 1 to n). A source is a vertex with no incoming edges, and a sink is the vertex with no outgoing edges. Note that a vertex could be the sink and the source simultaneously. In the wizards' graph the number of the sinks and the sources is the same.

Wizards numbered the sources in the order of increasing numbers of the vertices from 1 to k. The sinks are numbered from 1 to k in the similar way.

To make a bet, they, as are real wizards, cast a spell, which selects a set of k paths from all sources to the sinks in such a way that no two paths intersect at the vertices. In this case, each sink has exactly one path going to it from exactly one source. Let's suppose that the i-th sink has a path going to it from the a__i's source. Then let's call pair (i, j) an inversion if i < j and a__i > a__j. If the number of inversions among all possible pairs (i, j), such that (1 ≤ i < j ≤ k), is even, then the first wizard wins (the second one gives him one magic coin). Otherwise, the second wizard wins (he gets one magic coin from the first one).

Our wizards are captured with feverish excitement, so they kept choosing new paths again and again for so long that eventually they have chosen every possible set of paths for exactly once. The two sets of non-intersecting pathes are considered to be different, if and only if there is an edge, which lies at some path in one set and doesn't lie at any path of another set. To check their notes, they asked you to count the total winnings of the first player for all possible sets of paths modulo a prime number p.

在某个国家住着一些巫师，他们喜欢打一些奇怪的赌。

两名巫师画出一个包含 $n$ 个顶点和 $m$ 条边的有向无环图（DAG）（图中顶点编号为 $1$ 到 $n$）。源点（source）是指入度为 $0$ 的顶点，汇点（sink）是指出度为 $0$ 的顶点。注意：一个顶点可能同时是源点与汇点。在该巫师所画的图中，源点个数与汇点个数相等。

巫师将所有源点按其顶点编号从小到大排序，并依次编号为 $1$ 到 $k$；同样地，将所有汇点也按其顶点编号从小到大排序，并依次编号为 $1$ 到 $k$。

为了下注，他们——作为真正的巫师——施展了一个魔法咒语，该咒语从所有源点到所有汇点中选出一组 $k$ 条顶点不相交的路径（即任意两条路径在顶点上不相交）。此时，每个汇点恰好被一条路径到达，且该路径来自唯一的一个源点。假设第 $i$ 个汇点由第 $a_i$ 个源点出发的路径到达，则称数对 $(i, j)$ 是一个逆序对（inversion），当且仅当 $i < j$ 且 $a_i > a_j$。若所有满足 $1 \le i < j \le k$ 的数对 $(i, j)$ 中，逆序对的总数为偶数，则第一名巫师获胜（第二名巫师需付给他一枚魔法金币）；否则第二名巫师获胜（他从第一名巫师处获得一枚魔法金币）。

这两名巫师陷入狂热兴奋之中，反复不断选择新的路径组，直到他们恰好遍历了所有可能的路径组一次。两组顶点不相交路径被视为不同，当且仅当存在某条边，它出现在其中一组的某条路径中，但不出现在另一组的任何路径中。为核对他们的记录，他们请你计算：对所有可能的路径组，第一名巫师的总收益（即他赢的金币数减去他输的金币数）对给定质数 $p$ 取模的结果。

The first line contains three space-separated integers n, m, p (1 ≤ n ≤ 600, 0 ≤ m ≤ 105, 2 ≤ p ≤ 109 + 7). It is guaranteed that p is prime number.

Next m lines contain edges of the graph. Each line contains a pair of space-separated integers, a__i b__i — an edge from vertex a__i to vertex b__i. It is guaranteed that the graph is acyclic and that the graph contains the same number of sources and sinks. Please note that the graph can have multiple edges.

第一行包含三个以空格分隔的整数 $n$、$m$、$p$（$1 ≤ n ≤ 600$，$0 ≤ m ≤ 10^5$，$2 ≤ p ≤ 10^9 + 7$）。保证 $p$ 是质数。

接下来 $m$ 行描述图中的边。每行包含一对以空格分隔的整数 $a_i$、$b_i$，表示一条从顶点 $a_i$ 到顶点 $b_i$ 的有向边。保证该图是有向无环图（DAG），且图中源点（入度为 0 的顶点）的数量等于汇点（出度为 0 的顶点）的数量。请注意，图中可能存在重边。

Print the answer to the problem — the total winnings of the first player modulo a prime number p. Please note that the winnings may be negative, but the modulo residue must be non-negative (see the sample).

输出该问题的答案——第一位玩家的总赢利对质数 $p$ 取模的结果。请注意，赢利可能为负数，但模 $p$ 的剩余必须为非负数（参见样例）。

In the first sample, there is exactly one set of paths — . The number of inversions is 0, which is an even number. Therefore, the first wizard gets 1 coin.

In the second sample there is exactly one set of paths — . There is exactly one inversion. Therefore, the first wizard gets -1 coin. .

In the third sample, there are two sets of paths, which are counted with opposite signs.

In the fourth sample there are no set of paths at all.

In the fifth sample, there are three sources — the vertices with the numbers (2, 3, 5) and three sinks — the vertices with numbers (1, 2, 4). For a single set of paths are 2 inversions, that is, their number is even.

在第一个样例中，恰好存在一组路径——。逆序对数量为 0，是偶数。因此，第一位巫师获得 1 枚金币。

在第二个样例中，恰好存在一组路径——。恰好存在一个逆序对。因此，第一位巫师获得 -1 枚金币。。

在第三个样例中，存在两组路径，它们的贡献符号相反。

在第四个样例中，根本不存在任何路径组。

在第五个样例中，存在三个源点——编号为 (2, 3, 5) 的顶点，以及三个汇点——编号为 (1, 2, 4) 的顶点。对于唯一的一组路径 ，存在 2 个逆序对，即其数量为偶数。