Problem Statement

The Kingdom of Barutoku has $N$ towns numbered from $1$ to $N$.
There are $M$ roads in the whole kingdom, and the $i$-th road bidirectionally connects town $u_i$ and town $v_i$.
Each town is always connected by a bidirectional road to at least $1$ other town, and it is guaranteed that all towns can reach one another using the roads.
Also, there is at most $1$ road between any pair of towns, and no road starts and ends at the same town.

Baru, a boy who loves adventure, is in town $1$ on day $1$.
On each day from day $2$ onward, Baru chooses $1$ of the roads connected to his current town uniformly at random, takes it, and moves to the town he visits that day.
The moves on different days are independent.

One day, the kingdom's fortune teller told Baru the following.

"On day $S$, you will certainly visit town $A$."

Given that this prophecy is true, find the conditional probability that Baru visited town $B$ on day $T$ ($1 \leq T < S$), $\textrm{mod }998244353$.
It is guaranteed that the conditional probability is uniquely defined under the constraints of this problem.

Constraints

• $2 \leq N \leq 50$
• $N-1 \leq M \leq \dfrac{N(N-1)}{2}$
• $1 \leq u_i,\ v_i \leq N$, $u_i \neq v_i$ (no self-loops)
• $\{u_i,\ v_i\} \neq \{u_j,\ v_j\}$ when $i \neq j$ (no multiple edges)
• Each town is always connected by a bidirectional road to at least $1$ other town
• All towns can reach one another using the roads (the towns are connected)
• $1 \leq A ,\ B \leq N$
• $1 \leq T < S \leq 10^{18}$
• It is guaranteed that the probability that Baru is in town $A$ on day $S$ is not $0$
• It is guaranteed that the probability that Baru is in town $A$ on day $S$ is not $0$ modulo $\textrm{mod }998244353$
• The desired conditional probability can be expressed as an irreducible fraction whose denominator is coprime to $998244353$
• All inputs are integers

Input

$N\ M$  
$u_1\ v_1$　 
$u_2\ v_2$　 
$\vdots$   
$u_M\ v_M$   
$S\ T\ A\ B$   

Output

Output the desired conditional probability $\textrm{mod }998244353$ on $1$ line.
End the output with a newline.

Sample

Sample 1

Input

4 3
1 2
2 3
2 4
5 3 1 3

Output

332748118

The towns are arranged as follows.

Starting from town $1$ on day $1$, the position on each day is as follows.

• Day $1$: in town $1$ (probability $1$)
• Day $2$: in town $2$ (probability $1$)
• Day $3$: in one of towns $1, 3, 4$ (each with probability $\dfrac{1}{3}$)
• Day $4$: in town $2$ (probability $1$)
• Day $5$: in one of towns $1, 3, 4$ (each with probability $\dfrac{1}{3}$)

Thus, the calculation is as follows.

Numerator $$= P(\text{town 3 on day 3} \land \text{town 1 on day 5}) = \dfrac{1}{3} \times \dfrac{1}{3} = \dfrac{1}{9}$$(This calculation holds because these two events happen to be independent in this case.)

Denominator $$ = P(\text{town 1 on day 5}) = \dfrac{1}{3}$$

From this, the desired conditional probability is obtained as $$\dfrac{\frac{1}{9}}{\frac{1}{3}} = \dfrac{1}{3}$$

Since $3 \times 332748118 \equiv 1 \pmod{998244353}$, the output is $332748118$.

10 20
1 5
1 7
1 9
1 10
2 5
2 6
2 7
3 4
3 6
4 5
4 6
4 7
4 8
4 9
4 10
5 7
6 8
6 10
8 9
8 10
500 100 1 1

629589520

10 45
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
3 4
3 5
3 6
3 7
3 8
3 9
3 10
4 5
4 6
4 7
4 8
4 9
4 10
5 6
5 7
5 8
5 9
5 10
6 7
6 8
6 9
6 10
7 8
7 9
7 10
8 9
8 10
9 10
1000000000000000000 333333333333333333 3 8

312640670