#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) int((x).size())
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

#ifdef LOCAL
auto operator<<(auto& o, auto x) -> decltype(x.first, o);
auto operator<<(auto& o, auto x) -> decltype(x.end(), o) {
  o << "{";
  for (int i = 0; auto y : x) o << ", " + !i++ * 2 << y;
  return o << "}"; }
auto operator<<(auto& o, auto x) -> decltype(x.first, o) {
  return o << "(" << x.first << ", " << x.second << ")"; }
void __print(auto... x) { ((cerr << x << " "), ...) << endl; }
#define debug(x...) __print("[" #x "]:", x)
#else
#define debug(...) 2137
#endif

template<int M, int R>
struct Mod {
  static const int MOD = M, ROOT = R;
  int x;
  Mod(ll y = 0) : x(y % M) { x += (x < 0) * M; }
  Mod& operator+=(Mod o) {
    if ((x += o.x) >= M) x -= M;
    return *this; }
  Mod& operator-=(Mod o) {
    if ((x -= o.x) < 0) x += M;
    return *this; }
  Mod& operator*=(Mod o) {
    x = 1ll * x * o.x % M;
    return *this; }
  Mod& operator/=(Mod o) { return *this *= o.inv(); }
  friend Mod operator+(Mod a, Mod b) { return a += b; }
  friend Mod operator-(Mod a, Mod b) { return a -= b; }
  friend Mod operator*(Mod a, Mod b) { return a *= b; }
  friend Mod operator/(Mod a, Mod b) { return a /= b; }
  auto operator<=>(const Mod&) const = default;
  Mod pow(ll n) const {
    Mod a = x, b = 1;
    for (; n; n /= 2, a *= a) if (n & 1) b *= a;
    return b;
  }
  Mod inv() const { assert(x != 0); return pow(M - 2); }
};
using mint = Mod<1000003, -1>;

template<class T>
void ntt(vector<T>& a, bool inv) {
  int n = sz(a); vector<T> b(n);
  for (int i = n / 2; i; i /= 2, swap(a, b)) {
    T w = T(T::ROOT).pow((T::MOD - 1) / n * i), m = 1;
    for (int j = 0; j < n; j += 2 * i, m *= w) rep(k, 0, i) {
      T u = a[j + k], v = a[j + k + i] * m;
      b[j / 2 + k] = u + v, b[j / 2 + k + n / 2] = u - v;
    }
  }
  if (inv) {
    reverse(1 + all(a));
    T z = T(n).inv(); rep(i, 0, n) a[i] *= z;
  }
}
template<class T>
vector<T> conv(vector<T> a, vector<T> b) {
  int s = sz(a) + sz(b) - 1, n = 1 << __lg(2 * s - 1);
  a.resize(n); ntt(a, 0); b.resize(n); ntt(b, 0);
  rep(i, 0, n) a[i] *= b[i];
  ntt(a, 1); a.resize(s);
  return a;
}
template<class T>
vector<T> mconv(const auto& x, const auto& y) {
  auto con = [&](const auto& v) {
    vector<T> w(sz(v)); rep(i, 0, sz(v)) w[i] = v[i].x;
    return w; };
  return conv(con(x), con(y));
}
template<class T>
vector<T> conv3(const vector<T>& a, const vector<T>& b) {
  using m0 = Mod<754974721, 11>; auto c0 = mconv<m0>(a, b);
  using m1 = Mod<167772161, 3>;  auto c1 = mconv<m1>(a, b);
  using m2 = Mod<469762049, 3>;  auto c2 = mconv<m2>(a, b);
  int n = sz(c0); vector<T> d(n); m1 r01 = m1(m0::MOD).inv();
  m2 r02 = m2(m0::MOD).inv(), r12 = m2(m1::MOD).inv();
  rep(i, 0, n) {
    int x = c0[i].x, y = ((c1[i] - x) * r01).x,
        z = (((c2[i] - x) * r02 - y) * r12).x;
    d[i] = (T(z) * m1::MOD + y) * m0::MOD + x;
  }
  return d;
}

vector<mint> _f = {1}, _fi = {1};
void _init(int n) {
  int k = ssize(_f);
  if (n < k) return;
  n *= 2;
  _f.resize(n + 1);
  _fi.resize(n + 1);
  for (int i = k; i <= n; i++) _f[i] = _f[i - 1] * i;
  _fi[n] = _f[n].inv();
  for (int i = n; i > k; i--) _fi[i - 1] = _fi[i] * i;
}
mint fact(int n) {
  _init(n);
  return _f[n];
}
mint inv_fact(int n) {
  _init(n);
  return _fi[n];
}
mint choose(int n, int k) {
  if (n < k || k < 0) return 0;
  _init(n);
  return _f[n] * _fi[k] * _fi[n - k];
}

const int N = 100100;
int n, m;
int in[N], out[N], t;
vi adj[N];
mint dp[N][2][2];
int k[N];
mint pr[N];

vector<mint> rec(auto& x, int l, int r) {
  if (l + 1 == r) return x[l];
  int mid = (l + r) / 2;
  return conv3(rec(x, l, mid), rec(x, mid, r));
}

void dfs(int u, int p) {
  in[u] = t++;
  vector<vector<mint>> w;
  w.push_back({1});
  int kto = -1;
  for (int v : adj[u]) {
    if (v == p) continue;
    if (in[v] == -1) {
      dfs(v, u);
      if (k[v] != -1 && k[v] != u) {
          kto = v;
        } else {
          auto& x = w.emplace_back(3);
          rep(i, 0, 2) rep(j, 0, 2) x[i + j] += dp[v][i][j];
      }
    } else if (in[v] < in[u]) {
      k[u] = v;
    }
  }
  debug(u, kto);
  if (kto != -1) {
    k[u] = k[kto];
    rep(s, 0, 2) {
      auto& x = w.emplace_back(3);
      rep(i, 0, 2) x[i] += dp[kto][i][s];
      auto q = rec(w, 0, sz(w));
      rep(i, 0, sz(q)) {
        if (i % 2 == 0) {
          dp[u][1][s] += q[i] * pr[i];
        } else {
          dp[u][0][s] += q[i] * pr[i - 1] * i;
        }
      }
      w.pop_back();
    }
  } else {
    auto q = rec(w, 0, sz(w));
    rep(i, 0, sz(q)) rep(j, 0, 2) rep(b, 0, 2) {
      if (b && k[u] == -1) continue;
      if ((i + !j + (!b && k[u] != -1)) % 2) continue;
      dp[u][j][b] += q[i] * pr[i + !j + (!b && k[u] != -1)];
    }
  }
  rep(i, 0, 2) rep(j, 0, 2) debug(u, i, j, dp[u][i][j].x);
  debug(u, k[u]);
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  rep(i, 0, m) {
    int u, v;
    cin >> u >> v;
    u--; v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  rep(i, 0, n) in[i] = k[i] = -1;
  pr[0] = 1;
  rep(i, 1, n + 1) {
    if (i % 2 == 0) {
      pr[i] = (i - 1) * pr[i - 2];
    }
  }
  dfs(0, -1);
  //rep(i, 0, n) rep(j, 0, 2) rep(k, 0, 2) debug(i, j, k, dp[i][j][k].x);
  cout << dp[0][1][0].x << '\n';
}