#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll N, M, A, B;
ll G;
ll inv_A;

ll MOD = 119<<23|1;

vector<vector<ll>> adj;

// modular inverse with egcd
// get a^-1LL mod b
ll Modinverse(ll a, ll b) {
    ll r0 = a, r1LL = b;
    ll t0 = 1LL, t1LL = 0;
    while (r1LL) {
        ll q = r0 / r1LL;
        ll r = r0 - q * r1LL;
        ll t = t0 - q * t1LL;
        r0 = r1LL; r1LL = r;
        t0 = t1LL; t1LL = t;
    }
    t0 = (t0 % b + b) % b;
    return t0;
}

ll get_dp(ll height, ll width, vector<vector<ll>>& adj_type1, vector<vector<ll>>& adj_type2) {
    ll bitlen1 = B + 1LL;
    ll bitlen2 = 2 * (height + 1LL);
    ll half_bitlen2 = bitlen2 / 2;

    if (bitlen1 <= bitlen2) {
        vector<ll> dp(1LL << bitlen1, 0);
        dp[0] = 1LL;
        for (ll i = 0; i < adj_type1.size(); ++i) {
            vector<ll> new_dp(1LL << bitlen1, 0);
            for (ll prev_mask = 0; prev_mask < (1LL << bitlen1); ++prev_mask) {
                if (dp[prev_mask] == 0) {
                    continue;
                }
                // transition without connecting the current point
                new_dp[prev_mask >> 1LL] = (new_dp[prev_mask >> 1LL] + dp[prev_mask]) % MOD;
                // transition with connecting the current point
                for (auto next : adj_type1[i]) {
                    ll pos_diff = i - next;
                    if (prev_mask & (1LL << (bitlen1 - pos_diff))) {
                        continue;
                    }
                    ll next_mask = (prev_mask >> 1LL) | (1LL << (bitlen1 - 1LL));
                    if (bitlen1 - pos_diff > 0) {
                        next_mask |= (1LL << (bitlen1 - pos_diff - 1LL));
                    }
                    new_dp[next_mask] = (new_dp[next_mask] + dp[prev_mask]) % MOD;
                }
            }
            dp = new_dp;
        }
        ll ans = 0;
        for (auto x : dp) {
            ans = (ans + x) % MOD;
        }
        return ans;
    }
    else {
        vector<ll> dp(1LL << bitlen2, 0);
        dp[0] = 1LL;
        for (ll i = 0; i < half_bitlen2; ++i) {
            vector<ll> new_dp(1LL << bitlen2, 0);
            // half mask. 
            for (ll prev_mask = 0; prev_mask < (1LL << half_bitlen2); ++prev_mask) {
                if (dp[prev_mask | (prev_mask << half_bitlen2)] == 0) {
                    continue;
                }
                ll prev_complete_mask = prev_mask | (prev_mask << half_bitlen2);
                ll next_mask = prev_mask >> 1LL;
                ll next_complete_mask = next_mask | (next_mask << half_bitlen2);
                // transition without connecting the current point
                new_dp[next_complete_mask] = (new_dp[next_complete_mask] + dp[prev_complete_mask]) % MOD;
                // transition with connecting the current point
                for (auto next : adj_type2[i]) {
                    ll pos_diff = i - next;
                    if (prev_mask & (1LL << (half_bitlen2 - pos_diff))) {
                        continue;
                    }
                    ll next_mask = (prev_mask >> 1LL) | (1LL << (half_bitlen2 - 1LL));
                    if (half_bitlen2 - pos_diff > 0) {
                        next_mask |= (1LL << (half_bitlen2 - pos_diff - 1LL));
                    }
                    new_dp[next_mask | (next_mask << half_bitlen2)] = (new_dp[next_mask | (next_mask << half_bitlen2)] + dp[prev_complete_mask]) % MOD;
                }
            }
            dp = new_dp;
        }
        for (ll i = half_bitlen2; i < adj_type2.size(); ++i) {
            vector<ll> new_dp(1LL << bitlen2, 0);
            // half mask. 
            for (ll prev_mask = 0; prev_mask < (1LL << bitlen2); ++prev_mask) {
                if (dp[prev_mask] == 0) {
                    continue;
                }
                // represents the first half_bitlen2 bits of the mask : first elements
                ll upper_mask = prev_mask >> half_bitlen2;
                // represents the part where we're looking at
                ll lower_mask = prev_mask & ((1LL << half_bitlen2) - 1LL);
                // transition without connecting the current point
                new_dp[(upper_mask << half_bitlen2) | (lower_mask >> 1LL)] = (new_dp[(upper_mask << half_bitlen2) | (lower_mask >> 1LL)] + dp[prev_mask]) % MOD;
                // transition with connecting the current point
                for (auto next : adj_type2[i]) {
                    bool is_in_upper = next < half_bitlen2;
                    bool is_in_lower = (i - next) <= half_bitlen2;
                    assert(is_in_upper || is_in_lower);
                    bool is_next_occupied = false;
                    if (is_in_upper && (upper_mask & (1LL << next))) {
                        is_next_occupied = true;
                    }
                    if (is_in_lower && (lower_mask & (1LL << (half_bitlen2 - (i - next))))) {
                        assert(!is_in_upper || is_next_occupied);
                        is_next_occupied = true;
                    }
                    if (is_next_occupied) {
                        continue;
                    }
                    ll next_upper_mask = upper_mask;
                    ll next_lower_mask = lower_mask;
                    if (is_in_upper) {
                        next_upper_mask |= (1LL << next);
                    }
                    if (is_in_lower) {
                        next_lower_mask |= (1LL << (half_bitlen2 - (i - next)));
                    }
                    next_lower_mask >>= 1LL;
                    next_lower_mask |= (1LL << (half_bitlen2 - 1LL));
                    new_dp[(next_upper_mask << half_bitlen2) | next_lower_mask] = (new_dp[(next_upper_mask << half_bitlen2) | next_lower_mask] + dp[prev_mask]) % MOD;
                }
            }
            dp = new_dp;
        }
        ll ans = 0;
        for (auto x : dp) {
            ans = (ans + x) % MOD;
        }
        return ans;
    }

}

pair<ll, ll> get_idx(ll p) {
    p = p / G;
    return {p / B, (p * inv_A) % B};
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N >> M >> A >> B;

    adj.resize(N);

    for (ll i = 0; i < M; i++) {
        ll u, v;
        cin >> u >> v;
        --u; --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    G = gcd(A, B);
    A /= G;
    B /= G;
    inv_A = Modinverse(A, B);

    ll ans = 1LL;

    // process points with remainder i when divided by G
    for (ll i = 0; i < G; ++i) {
        vector<ll> points;
        for (ll j = i; j < N; j += G) {
            points.push_back(j);
        }
        ll grid_height = max(2LL, (ll)(points.size() + B - 1LL) / B);
        vector<vector<ll>> adj_2d_type1(grid_height * B, vector<ll>()), adj_2d_type2(grid_height * B, vector<ll>());
        for (ll j = 0; j < points.size(); ++j) {
            auto [idx, jdx] = get_idx(points[j]);
            for (auto next : adj[points[j]]) {
                auto [next_idx, next_jdx] = get_idx(next);
                if (next_idx * B + next_jdx < idx * B + jdx) {
                    adj_2d_type1[idx * B + jdx].push_back(next_idx * B + next_jdx);
                }
                if (next_idx + next_jdx * grid_height < idx + jdx * grid_height) {
                    adj_2d_type2[jdx * grid_height + idx].push_back(next_jdx * grid_height + next_idx);
                }
            }
        }
        ans = ans * get_dp(grid_height, B, adj_2d_type1, adj_2d_type2) % MOD;
    }

    cout << ans << "\n";

    return 0;
}