A directed graph $G = (V, E)$ is called semi-connected if for any two vertices $u, v \in V$, there exists a directed path from $u$ to $v$ or a directed path from $v$ to $u$.

If $G' = (V', E')$ satisfies $V' \subseteq V$ and $E'$ contains all edges in $E$ that connect two vertices in $V'$, then $G'$ is called an induced subgraph of $G$.

If $G'$ is an induced subgraph of $G$ and $G'$ is semi-connected, then $G'$ is called a semi-connected subgraph of $G$.

If $G'$ is a semi-connected subgraph of $G$ that contains the maximum number of vertices among all semi-connected subgraphs of $G$, then $G'$ is called a maximum semi-connected subgraph of $G$.

Given a directed graph $G$, find the number of vertices $K$ in a maximum semi-connected subgraph of $G$, and the number of different maximum semi-connected subgraphs $C$. Since $C$ can be very large, you are only required to output $C \pmod X$.

Input

The first line contains three integers $N, M, X$. $N$ and $M$ represent the number of vertices and edges in graph $G$, respectively, and $X$ is as defined above. The following $M$ lines each contain two positive integers $a, b$, representing a directed edge $(a, b)$. Each vertex in the graph is numbered $1, 2, 3, \dots, N$. It is guaranteed that the same edge $(a, b)$ will not appear twice in the input.

Output

The output should contain two lines. The first line contains an integer $K$. The second line contains the integer $C \pmod X$.

Constraints

• For 20% of the data: $N \le 18$
• For 60% of the data: $N \le 10000$
• For 100% of the data: $N \le 100000, M \le 1000000$
• For 100% of the data: $X \le 10^8$

Examples

Input 1

6 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4

Output 1

3
3