Non‐Crossing Bird Assignments

In Byteotia there are two extremely tall trees. On each tree trunk there are many holes located at distinct heights. There are n birds that can fly very fast and have decided to live in these holes. Some pairs of birds know each other, and because of that they wish to visit the holes of the birds they know. Since the birds fly along straight lines and wish to avoid mid‐air collisions, they agree on the following conditions when choosing their homes:

• For every pair of birds that know each other, the birds must live in different trees.
• If two birds (say bird i and bird j) are assigned to different trees then we imagine that they occupy the lowest available holes of their chosen tree. In other words, if a tree has d birds then the holes used are exactly the d lowest ones. Consequently the vertical order on each tree is fixed by the natural order of bird indices (that is, the bird with a smaller index occupies a lower hole than a bird with a larger index, if both reside in the same tree).
• For every two acquaintance pairs, when we draw the straight‐line segment connecting the two corresponding holes (one on each tree), no two such segments should cross (although they may share an endpoint). Formally, let an edge connecting bird u and bird v be drawn as follows: if one bird is assigned to the left tree and the other to the right tree, then let the bird living in the left tree be the left endpoint and the one in the right tree be the right endpoint. Then if there are two acquaintance pairs having endpoints (u, v) and (x, y) (with u and x on the left tree and v and y on the right tree), and if u < x then we must have v ≤ y (note that equality is allowed since sharing an endpoint is permitted).

Your task is to calculate, modulo k, the total number of assignments of birds to the two trees that satisfy the conditions above. It is guaranteed that there are more holes available than birds.

The mathematical conditions can be summarized using LaTeX as follows:

If we denote an assignment by a function \(f : \{1,2,\dots,n\} \to \{L,R\}\) then for every acquaintance pair \((i,j)\) we must have \[ f(i) \neq f(j), \] and if we define for each edge the ordered pair \[ (u,v) = \begin{cases}\,(i,j) &\text{if } f(i)=L \text{ and } f(j)=R,\\ (j,i) &\text{if } f(i)=R \text{ and } f(j)=L, \end{cases} \] then after sorting these pairs by the first coordinate, if \((u_1,v_1), (u_2,v_2),\dots,(u_t,v_t)\) is the sequence with \(u_1 \le u_2 \le \cdots \le u_t\), it must hold that for every \(1 \le i < t\), if \(u_i < u_{i+1}\) then \(v_i \le v_{i+1}\).

inputFormat

The first line contains three integers n, m and k \((1 \le n \le 20,\ 0 \le m \le \frac{n(n-1)}{2},\ 1 \le k \le 10^9)\) -- the number of birds, the number of pairs of birds that know each other, and the modulus.

Each of the next m lines contains two distinct integers u and v \((1 \le u,v \le n)\) indicating that bird u and bird v know each other. Each pair appears at most once.

outputFormat

Output a single integer, the number of valid assignments modulo k.

sample

3 2 1000
1 3
2 3

2