Problem I
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\le N\le 50000$, $0\le M\le 1.5N$, $1\le k\le {10}^9$, $1\le P\le 2\cdot {10}^9$). The next $M$ lines of input each contains a pair of integers $A$ and $B$ ($1\le A\le N$, $1\le B\le 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