Cho đơn đồ thị vô hướng gồm \(N\) đỉnh (được đánh số từ \(1\) đến \(N\)) và \(M\) cạnh (được đánh số từ \(1\) đến \(M\)). Cạnh thứ \(i\) nối hai đỉnh \(u_i\) và \(v_i\). Cho biết các số nguyên \(K\), \(S\), \(T\), và \(X\), bạn hãy đếm số lượng đường đi \((A_0, A_1, A_2,..., A_K)\) thỏa mãn các điều kiện:

• \(A_0=S\) và \(A_K=T\).
• Đỉnh \(X\) xuất hiện một số chẵn lần (có thể là \(0\)) trên toàn đường đi.

Vì kết quả có thể rất lớn nên bạn chỉ cần in ra phần dư của nó khi chia cho \(998244353\).

Input

• Dòng đầu chứa sáu số nguyên \(N\), \(M\), \(K\), \(S\), \(T\), và \(X\) \((2\le N\le 2000, 1\le M\le 2000, 1\le S,T,X\le N, 1\le K\le 2000)\).
• Dòng thứ \(i\) trong \(M\) dòng tiếp theo chứa hai số nguyên \(u_i\) và \(v_i\) \((1\le u_i\ne v_i\le N)\).

Output

• In ra số lượng đường đi thỏa mãn \(\text{MOD}\) \(998244353\).

Ví dụ

Sample input 01

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

Sample output 01

4

Giải thích

04 đường đi thỏa mãn là:

• \((1,2,1,2,3)\)
• \((1,2,3,2,3)\)
• \((1,4,1,4,3)\)
• \((1,4,3,4,3)\)