#include <bits/stdc++.h>

constexpr int N = 500005;
const int mod = 0x3b800001;

int n, m, tot;
std::set<int> G[N];
std::map<std::pair<int, int>, int> id;
int u[N << 1], v[N << 1], f[N << 1], g[N << 1];

inline int &to(int uu, const int &id) {
    return uu == u[id] ? v[id] : u[id];
}

int deg[N];

inline int add_e(int uu, int vv, int ff, int gg) {
    ++tot;
    u[tot] = uu;
    v[tot] = vv;
    G[uu].emplace(tot);
    G[vv].emplace(tot);
    id[std::make_pair(uu, vv)] = id[std::make_pair(vv, uu)] = tot;
    deg[uu]++;
    deg[vv]++;
    f[tot] = ff;
    g[tot] = gg;
    return tot;
}


inline void del(int id) {
    G[u[id]].erase(id);
    G[v[id]].erase(id);
    deg[u[id]]--;
    deg[v[id]]--;
}

int main() {
    std::cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        std::cin >> u[i] >> v[i];
        G[u[i]].emplace(i);
        G[v[i]].emplace(i);
        deg[u[i]]++;
        deg[v[i]]++;
        f[i] = g[i] = 1;
        id[std::make_pair(u[i], v[i])] = id[std::make_pair(v[i], u[i])] = i;
    }
    tot = m;
    std::queue<int> q;
    for (int i = 1; i <= n; i++) 
        if (deg[i] <= 2)
            q.push(i);
    int ans = 1;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        if (!deg[x]) break;
        if (deg[x] == 1) {
            assert((int)G[x].size() == 1);
            int idd = *G[x].begin();
            del(idd);
            ans = 1ll * ans * f[idd] % mod;
            continue;
        } else {
            assert(deg[x] == 2);
            int id1 = *G[x].begin(), id2 = *std::next(G[x].begin());
            int u = to(x, id1), v = to(x, id2);
            del(id1);
            del(id2);

            int ff = 1ll * f[id1] * f[id2] % mod, gg = (1ll * f[id1] * g[id2] + 1ll * g[id1] * f[id2]) % mod;
            if (!id.count(std::make_pair(u, v))) {
                add_e(u, v, ff, gg);
            } else {
                int idd = id[std::make_pair(u, v)];
                int tmpf = f[idd], tmpg = g[idd];
                f[idd] = (1ll * tmpf * gg + 1ll * ff * tmpg) % mod;
                g[idd] = 1ll * tmpg * gg % mod;
                if (deg[u] <= 2) q.push(u);
                if (deg[v] <= 2) q.push(v);
            }
        }
    }
    std::cout << ans << '\n';
}