Problem H
k-Colouring of a Graph

You are given a simple graph with $N$ nodes and $M$ edges. The graph has the special property that any connected component of size $s$ contains no more than $s + 2$ edges. You are also given two integers $k$ and $P$. Find the number of $k$-colourings of the graph, modulo $P$.

Recall that a simple graph is an undirected graph with no self loops and no repeated edges. A $k$-colouring of a graph is a way to assign to each node of the graph exactly one of $k$ colours, such that if edge $(u, v)$ is present in the graph, then $u$ and $v$ receive different colors.

Input

The first line of input consists of four integers, $N, M, k$, and $P$ ($1 \leq N \leq 50\, 000$, $0 \leq M \leq 1.5 N$, $1 \leq k \leq 10^9$, $1 \leq P \leq 2 \cdot 10^9$). The next $M$ lines of input each contains a pair of integers $A$ and $B$ ($1 \leq A \leq N$, $1 \leq B \leq N$), describing an edge in the graph connecting nodes $A$ and $B$.

Output

Output the number of $k$-colourings of the given graph, modulo $P$.

3 3 2 10000
1 2
2 3
3 1

0

3 3 4 13
1 2
2 3
3 1

11