Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

It is a period of civil war. Rebel spaceships, striking from a hidden base, have won their first victory against the evil Galactic Empire. 

In light of these events, Chef, the leader of the rebel alliance, wants to build safe connections in galaxy with N stars. There are M bidirectional space roads in space that connect pairs of stars together. Travelling through one space road takes 1 day. 

To avoid detection by the Empire, Chef decided that rebels must never travel alone. Instead, they must travel using armored rebel spaceships. Each spaceship is designated two stars, and a fixed route between these stars. A route is just a path composed of roads that connects two stars, but to increase security, Chef added the following restrictions on routes:

Each route must be traversable within at most K days.
Roads may be traversed any number times in a single route, in both directions.

After some time has passed, Chef and his engineers were able to build a spaceship for every possible route between stars.

Unfortunately, the powerful Empire discovered this and plans to destroy these spaceships to maintain control of the galaxy. Specifically, they deployed a new superweapon called the Death Starkiller Base, which is able to destroy X spaceships at once! It works by analyzing all spaceships that pass through Empire-controlled star systems.

Unfortunately, since the destruction of the Empire's two previous superweapons, the budget for the new superweapon is crippled, so the Death Starkiller Base has some severe restrictions:

It can only destroy exactly X spaceships per usage. Not more, not less.
It can only destroy a group of spaceships if they travel between the same pair of stars.

Despite these flaws, the Empire still used the superweapon as many times as possible, until there aren't enough groups of spaceships any more to destroy.

To avoid more casualties, Chef decided to retire most of the surviving spaceships. Chef wants to retire as many spaceships as possible, but in order to stay connected, Chef wants to do this such that there is still a way to get from any star to another using spaceships. How many ways are there for Chef to retire spaceships so that this is satisfied?

Note that a spaceship can only pick up or drop off people at the start or end of its journey, so a single spaceship that happens to pass through all stars isn't enough (unless there are only two stars).

------ Input ------ 

The first line of input contains four positive integers - N, M, X, K. The next M lines each contains two integers U, V stars which connect by space road. All space roads are pairwise distinct.

------ Output ------ 

Output a single line containing a single integer — the solution of Chef's problem.

------ Constraints ------ 

$1 ≤ N ≤ 100$
$0 ≤ M ≤ Nx(N-1)/2$
$1 ≤ K ≤ 10^{18}$
$1 ≤ X ≤ 7777777$
$1 ≤ U < V ≤ N $
$ Each space road (U, V) will be in input at most once. $

------ Subtasks ------ 

$Subtask 1: (10 pts) N ≤ 5.$Subtask 2: (25 pts) N ≤ 30.$Subtask 3: (65 pts) Original constraints. 

------ Example ------ 

Input:
3 3 100 3
1 2
2 3
3 1

Output:
75

Input:
3 3 2 3
1 2
2 3
3 1

Output:
3

Input:
5 8 10000 1000000000
4 5
3 5
1 4
1 3
2 3
2 4
1 2
1 5

Output:
2220611572265625

------ Explanation: ------ 

Example case 1. There are five possible routes between stars 1 and 2 traversable in not more than 3 days: {1-2, 1-3-2, 1-2-1-2, 1-2-3-2, 1-3-1-2}. There are also five routes between stars 2 and 3, and also between stars 1 and 3. There are three possible plans for the remaining routes:

$A route remains between 1 and 2, and between 2 and 3. There are 5 x 5 = 25 ways to do this.$
$A route remains between 2 and 3, and between 3 and 1. There are 5 x 5 = 25 ways to do this.$
$A route remains between 3 and 1, and between 1 and 2. There are 5 x 5 = 25 ways to do this.$

All in all, there are 25 + 25 + 25 = 75 plans.

Difficulty: VERY_HARD
Tags: Number theory

Dynamic programming

Matrices

Mathematics
Skill types: Dynamic programming

Starter code:

Solutions:
import sys
import numpy as np

def mpow_mod(M, k, mod):
	ret = np.identity(M.shape[0], dtype=np.int64)
	while k > 0:
		if k & 1:
			ret = ret.dot(M)
			ret %= mod
		M = M.dot(M)
		M %= mod
		k >>= 1
	return ret

def lap(M):
	n = M.shape[0]
	L = np.zeros((n, n), dtype=np.int64)
	L[range(n), range(n)] = np.sum(M, 0)
	L -= M
	return L

def int_array(m):
	ret = np.array([int(x) for x in m.flat], dtype=object)
	ret = ret.reshape(m.shape)
	return ret

def mred(m):
	n = m.shape[0]
	ret = m[1:, 1:]
	for i in range(n - 1):
		for j in range(n - 1):
			ret[i, j] = m[0, 0] * m[i + 1, j + 1] - m[i + 1, 0] * m[0, j + 1]
	return ret

def det(m):
	a = 1
	while m.shape[0] > 1:
		b = m[0, 0]
		if a == 0:
			return 0
		m = mred(m) // a
		a = b
	return m[0, 0]

def solve(M, k, x):
	n = M.shape[0]
	I = np.identity(n, dtype=np.int64)
	M0 = np.vstack((np.hstack((M, I)), np.hstack((I * 0, I))))
	M1 = mpow_mod(M0, k + 1, x)[:n, n:]
	M1[range(n), range(n)] = 0
	if n == 1:
		return 1
	if n == 2:
		return M1[0, 1]
	L = lap(M1)[1:, 1:]
	return det(int_array(L))
f = sys.stdin
(n, m, x, k) = map(int, f.readline().split())
M = np.zeros((n, n), dtype=np.int64)
for i in range(m):
	(a, b) = map(int, f.readline().split())
	M[a - 1, b - 1] = M[b - 1, a - 1] = 1
print(solve(M, k, x))