#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = , mod = 1e9 + ;

int n, m, cnt1, cnt2, head[maxn], to[maxn], nextt[maxn], tot = ;

bool vis[maxn], vis2[maxn];

long long ans = ;

void add(int x, int y)

{

    to[tot] = y;

    nextt[tot] = head[x];

    head[x] = tot++;

}

void dfs(int u)

{

    vis[u] = ;

    cnt1++;

    for (int i = head[u]; i; i = nextt[i])

    {

        int t = i, t2;

        if (t %  == )

            t2 = i - ;

        else

            t2 = i + ;

        if (!vis2[i])

        {

            cnt2++;

            vis2[t] = vis2[t2] = ;

        }

        int v = to[i];

        if (!vis[v])

            dfs(v);

    }

}

int main()

{

    scanf("%d%d", &n, &m);

    for (int i = ; i <= m; i++)

    {

        int u, v;

        scanf("%d%d", &u, &v);

        add(u, v);

        add(v, u);

    }

    for (int i = ; i <= n; i++)

    {

        if (!vis[i])

        {

            cnt1 = ;

            cnt2 = ;

            dfs(i);

            if (cnt1 == cnt2)

            {

                if (ans == )

                    ans = ;

                else

                    ans = (ans * ) % mod;

            }

            if (cnt1 == cnt2 + )

            {

                if (ans == )

                    ans = cnt1;

                else

                    ans = (ans * cnt1) % mod;

            }

        }

    }

    printf("%lld\n", ans);

    return ;

}