408067: GYM102978 E Edge Subsets

You are given integers $$$A,B$$$, and a simple undirected graph of $$$N$$$ vertices and $$$M$$$ edges. The vertices are numbered from $$$1$$$ through $$$N$$$, and the edges from $$$1$$$ through $$$M$$$. The edge $$$i$$$ connects the vertices $$$U_i$$$ and $$$V_i$$$. Here, it is guaranteed that $$$V_i-U_i=A$$$ or $$$V_i-U_i=B$$$.

Find the number of matchings of the graph, modulo $$$998244353$$$. Note that a matching of the graph is a subset of edges whose end-points are all distinct.

The first line contains integers $$$N$$$ ($$$3 \leq N \leq 200$$$), $$$M$$$ ($$$1 \leq M \leq 400$$$), $$$A$$$, and $$$B$$$ ($$$1 \leq A < B \leq N-1$$$).

The following $$$M$$$ lines describe the edges. The $$$i$$$-th of those lines contains integers $$$U_i$$$ and $$$V_i$$$ ($$$1 \leq U_i < V_i \leq N$$$, $$$V_i-U_i=A$$$ or $$$V_i-U_i=B$$$). There are no self-loops or multi-edges.

Print the answer.

4 3 1 2
1 2
1 3
3 4

5

10 14 2 4
5 7
7 9
2 6
6 8
1 5
3 7
4 8
1 3
4 6
8 10
3 5
5 9
2 4
6 10

225