5403: Defend Ponyville

Changelings are going to attack Ponyville again! Their goal is to absorb the love inside all the ponies as their food! Unluckily, the defense of Ponyville is now too fragile to fight against them. Twilight Sparkle must reinforce the defense magic cast around Ponyville before Changelings' final attack.

There are nnn magic sources in Ponyville, together with m undirected connections. Each connection connects exactly 2 different magic sources, and there is at most 1 connection between 2 magic sources. The defense power is initially 0 . At any time, Twilight Sparkle can cast a spell to a set of n-1 connections ( the set cannot be empty ) that connects all the n sources (any source can reach other sources through these n-1 connections), and the defense power will increase by 1 . However, the same set of connections can be used only once every day to increase the defense power. The two sets are the same if and only if they have precisely the same connections. Twilight Sparkle only has t days to prepare before Changelings pour in, so every day she will gain as much defense power as possible.

But due to the unstable magic field, some connections may disappear in some days. Luckily, thanks to Twilight's research, we know that the probability for the j-th connection to exist on the i-th day (i=1,2,…,t)is q_j+(p_j−q_j)a⁻⁽ⁱ⁻¹⁾ (0≤p_j,q_j≤1,p_j≠q_j), where a is a given constant. Twilight Sparkle wants to know the expectation of total defense power she can gain in ttt days. Can you help her and protect Ponyville?

The first line contains 4 integers n,m,t,a (1≤n≤300,0≤m≤n(n−1)/2,1≤t≤10⁸,1≤a≤10⁹).

The following m lines are the m connections. The i-th line contains 6 integers u_i,v_i,a_1i,b_1i,a_2i,b_2i (1≤u_i,v_i≤n,u_i≠v_i,0≤a_1i,a_2i≤10⁹,1≤b_1i,b_2i≤10⁹), indicating that the i-th connection is between u_i and v_i , p_i=a_1i/b_1i,q_i=a_2i/b_2i (0≤p_j,q_j≤1,p_j≠q_j).

One integer indicating the expectation of the total defense power Twilight Sparkle can get. You should output the answer modulo 998244353. Formally, let M=998244353. It can be shown that the answer can be expressed as an irreducible fraction p/q, where p and q are integers and q  0 mod  M.Output the integer equal to p × q⁻¹ mod M. In other words, output such an integer x that 0≤ x < M and x⋅q ≡ p mod  M.

3 3 2 2
1 2 1 1 0 1
2 3 1 1 0 1
1 3 1 1 0 1

249561092