/*
WA因：状压13位而不是12位 
TLE因：优化一下存图方式，避免枚举13个点来检测是否可染色 

注意：只有合法状态有初值，且不合法状态不会被合法状态更新，所以 
不需要在更新的时候可以避免枚举不合法状态（当然对于计数题不用将其看作 
“不合法”，而是方案数为0） 
*/

#include <bits/stdc++.h>

using namespace std;

const int N = 55, S = 1600000;

int n, m;
int e[N], s[S][2];
int f[2][S];    // 滚一下 
int pw[N];

void add(int &a, int b) { a = (a + b) % 4; }

signed main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  
  cin >> n >> m;
  
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    if (u < v) swap(u, v);
    e[u] |= 1 << (u - v - 1);
  }
  
  pw[0] = 1;
  for (int i = 1; i <= 13; i++) pw[i] = pw[i - 1] * 3;
  
  // 处理颜色对照表  
  for (int i = 0; i < pw[13]; i++) {
    for (int j = 0; j < 13; j++) {
      int bit = i / pw[j] % 3;
      if (bit == 2) continue;
      s[i][bit] |= 1 << j;
    }
  }
  
  f[1][0] = f[1][1] = f[1][2] = 1;
  for (int i = 1; i < n; i++) {
//    int t = min(13, i);
    for (int j = 0; j < 13; j++) {
      int nj = (j - pw[12] * (j / pw[12])) * 3;   // 注意要超出13位才去尾 
      // 注意+1 
      if (!(e[i + 1] & s[j][1])) add(f[(i + 1) & 1][nj + 0], f[i & 1][j]);
      if (!(e[i + 1] & s[j][0])) add(f[(i + 1) & 1][nj + 1], f[i & 1][j]);
      add(f[(i + 1) & 1][nj + 2], f[i & 1][j]);
      f[i & 1][j] = 0;      // 滚动数组要清这个 
    }
  }
  
  int ans = 0;
  for (int j = 0; j < pw[13]; j++)
    add(ans, f[n & 1][j]);
  
  cout << ans / 2;
  
  return 0;
}