#include <bits/stdc++.h>

const int maxn = 50, maxd = 13, mod = 4;

std::array<int, maxn + 1> e;
std::array<std::array<std::array<short, 1 << maxd>, 1 << maxd>, 2> f;

void inc(short &x, short y) {
  if ((x += y) >= mod) {
    x -= mod;
  }
}

int main() {
  std::cin.tie(nullptr)->sync_with_stdio(false);

  int n, m;
  std::cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int u, v;
    std::cin >> u >> v;
    e[std::max(u, v)] |= 1 << (std::abs(u - v) - 1);
  }

  f[0 & 1][0][0] = 1;
  int all = (1 << maxd) - 1;
  for (int i = 1; i <= n; ++i) {
    for (int S = 0; S <= all; ++S) {
      for (int T = S; ; T = (T - 1) & S) {
        int R = S ^ T;
        f[i & 1][T][R] = 0;
        if (T == 0) {
          break;
        }
      }
    }
    for (int S = 0; S <= all; ++S) {
      for (int T = S; ; T = (T - 1) & S) {
        int R = S ^ T;
        inc(f[i & 1][(T << 1) & all][(R << 1) & all], f[(i - 1) & 1][T][R]);
        if ((e[i] & R) == 0) {
          inc(f[i & 1][(T << 1 | 1) & all][(R << 1) & all], f[(i - 1) & 1][T][R]);
        }
        if ((e[i] & T) == 0) {
          inc(f[i & 1][(T << 1) & all][(R << 1 | 1) & all], f[(i - 1) & 1][T][R]);
        }
        if (T == 0) {
          break;
        }
      }
    }
  }

  short ans = 0;
  for (int S = 0; S <= all; ++S) {
    for (int T = S; ; T = (T - 1) & S) {
      inc(ans, f[n & 1][T][S ^ T]);
      if (T == 0) {
        break;
      }
    }
  }
  std::cout << ans / 2 << "\n";
  return 0;
}