#include <bits/stdc++.h>
#define int long long
const int mod = 1594323;
int n, m, u, v, Vec[102], pow3[20], f[2000003][2], dp[50][2000003], ans;
std::vector<int> vec[103];
void init() {
    pow3[0] = 1, dp[0][0] = 1;
    for (int i = 1; i < 20; i++)
        pow3[i] = pow3[i - 1] * 3;
    printf("%lld\n", pow3[13]);
    for (int i = 0; i < mod; i++)
        for (int j = 0; j < 13; j++) {
            int nw = i / pow3[j] % 3;

            if (nw)
                f[i][nw - 1] |= (1 << j);
        }
}
signed main() {
    scanf("%lld%lld", &n, &m), init();
    for (; m--;) {
        scanf("%lld%lld", &u, &v), vec[u].push_back(v), vec[v].push_back(u);
        if (u > v)
            std::swap(u, v);
        Vec[v] |= (1 << v - u - 1);
    }
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= mod; j++) {
            dp[i][j * 3 % mod] = (dp[i][j * 3 % mod] + dp[i - 1][j]) % 4;
            if (!f[j][1] || !Vec[i])
                dp[i][j * 3 % mod + 2] =
                    (dp[i][j * 3 % mod + 2] + dp[i - 1][j]) % 4;
            if (!f[j][2] || !Vec[i])
                dp[i][j * 3 % mod + 1] =
                    (dp[i][j * 3 % mod + 1] + dp[i - 1][j]) % 4;
        }
    for (int i = 0; i < mod; i++)
        ans = (ans + dp[n][i]) % 4;
    printf("%lld", ans / 2);
    return 0;
}