#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2405"

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

#define call_from_test
#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif

#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
// Assume Connected
struct NiceTree{
  vector< vector<int> > G;
  vector< set<int> > ex;
  vector<int> buff;
  NiceTree(int n):G(n),ex(n),buff(n){}

  void add_edge(int u,int v){
    if(u>v) swap(u,v);
    if(ex[u].count(v)) return;
    G[u].emplace_back(v);
    G[v].emplace_back(u);
    ex[u].emplace(v);
  }

  enum Type{LEAF, JOIN, INTRODUCE, FORGET};
  struct Node{
    int type;

    // index for G
    vector<int> bag;
    void add_vertex(int v){bag.emplace_back(v);}

    // index for T
    vector<int> child;
    void add_child(int v){child.emplace_back(v);}
  };

  vector<Node> T;
  void to_nice(){
    for(auto &v:T)
      sort(v.bag.begin(),v.bag.end());

    stack<int> st;
    st.emplace(0);

    while(!st.empty()){
      int v=st.top();st.pop();

      while(T[v].child.size()>2){
        Node r;
        r.add_child(T[v].child.back());
        T[v].child.pop_back();
        r.add_child(T[v].child.back());
        T[v].child.pop_back();
        r.bag=T[v].bag;
        T[v].add_child(T.size());
        T.emplace_back(r);
      }

      if(T[v].child.size()==2){
        for(auto &u:T[v].child){
          if(T[u].bag!=T[v].bag){
            Node r;
            r.add_child(u);
            r.bag=T[v].bag;
            u=T.size();
            T.emplace_back(r);
          }
        }
        T[v].type=JOIN;
      }

      if(T[v].child.size()==1){
        int &u=T[v].child[0];
        vector<int> latte,malta;
        auto &ps=T[v].bag;
        auto &qs=T[u].bag;
        set_difference(ps.begin(),ps.end(),qs.begin(),qs.end(),
                       back_inserter(latte));
        set_difference(qs.begin(),qs.end(),ps.begin(),ps.end(),
                       back_inserter(malta));
        if(latte.size()+malta.size()>1){
          Node r;
          r.add_child(u);
          r.bag=T[v].bag;
          if(!latte.empty()){
            r.bag.erase(find(r.bag.begin(),r.bag.end(),latte.back()));
          }else{
            r.bag.emplace_back(malta.back());
          }
          u=T.size();
          T.emplace_back(r);
        }
        if(T[v].bag.size()<T[u].bag.size()) T[v].type=FORGET;
        if(T[v].bag.size()>T[u].bag.size()) T[v].type=INTRODUCE;
      }

      if(T[v].child.empty()){
        if(T[v].bag.size()>1){
          Node r;
          r.bag=T[v].bag;
          r.bag.pop_back();
          T[v].type=INTRODUCE;
          T[v].add_child(T.size());
          T.emplace_back(r);
        }else{
          T[v].type=LEAF;
        }
      }

      for(auto &u:T[v].child)
        st.emplace(u);
    }
  }

  // root = 0
  void build(){
    int n=G.size();
    if(n<=3){
      Node r;
      for(int i=0;i<n;i++) r.add_vertex(i);
      T=vector<Node>({r});
      return to_nice();
    }

    vector<int> deg(n);
    queue<int> que;
    for(int i=0;i<n;i++){
      deg[i]=G[i].size();
      if(deg[i]<=2) que.emplace(i);
    }

    vector<int> used(n,-1);
    T.emplace_back();
    while(!que.empty()){
      int v=que.front();que.pop();
      if(deg[v]>2||used[v]!=-1) continue;
      Node r;
      r.add_vertex(v);

      int p=-1,q=-1;
      for(int u:G[v]){
        if(used[u]==-1){
          (p==-1?p:q)=u;
          r.add_vertex(u);
        }else if(used[u]>=0){
          r.add_child(used[u]);
          used[u]=-2;
        }
      }

      if(deg[v]==0){
        used[v]=T.size();
        T.emplace_back(r);
        continue;
      }

      if(q==-1){
        deg[p]--;
      }else{
        if(p>q) swap(p,q);
        if(!ex[p].count(q)){
          add_edge(p,q);
        }else{
          deg[p]--;
          deg[q]--;
        }
      }
      for(int u:G[v])
        if(deg[u]<=2) que.emplace(u);
      deg[v]=0;
      used[v]=T.size();
      T.emplace_back(r);
    }

    for(int i=0;i<n;i++){
      if(deg[i]>0){
        T={};
        return;
      }
    }

    T.front()=T.back();T.pop_back();
    to_nice();
  }

  template<typename F1,typename F2,typename F3,typename F4>
  void dfs(int v,F1 &leaf,F2 &join,F3 &introduce,F4 &forget){
    const auto &chd=T[v].child;
    for(int u:chd) dfs(u,leaf,join,introduce,forget);

    if(T[v].type==LEAF){
      leaf(v);
      return;
    }
    if(T[v].type==JOIN){
      join(v);
      return;
    }

    const auto &bag=T[v].bag;
    for(int i=0;i<(int)bag.size();i++)
      buff[bag[i]]=1<<i;

    const auto &chd_bag=T[chd[0]].bag;
    int dif=0;
    for(int b:bag) dif^=b;
    for(int b:chd_bag) dif^=b;

    if(T[v].type==INTRODUCE){
      introduce(v,dif);
      return;
    }
    if(T[v].type==FORGET){
      forget(v,dif);
      return;
    }
  }
};
//END CUT HERE
#ifndef call_from_test

#define call_from_test
#include "../tools/fastio.cpp"
#include "../tools/chminmax.cpp"
#undef call_from_test

signed CSA_SPECIAL_MVC(){
  int n,m;
  cin>>n>>m;
  NiceTree G(n);
  using P = pair<int, int>;
  set<P> es;
  for(int i=0;i<m;i++){
    int a,b;
    cin>>a>>b;
    a--;b--;
    G.add_edge(a,b);
    es.emplace(a,b);
    es.emplace(b,a);
  }

  G.build();
  auto &T=G.T;
  auto &buff=G.buff;

  vector< vector<int> > dps(T.size());

  const int INF = 1e9;
  auto base=
    [&](int v){
      const auto &bag=T[v].bag;
      auto &dp=dps[v];
      dp.assign(1<<bag.size(),-INF);
    };

  auto leaf=
    [&](int v){
      base(v);
      auto &dp=dps[v];
      dp[0]=0;
      dp[1]=1;
    };

  auto join=
    [&](int v){
      base(v);
      const auto &chd=T[v].child;
      auto &dp=dps[v];
      for(int i=0;i<(int)dp.size();i++)
        chmax(dp[i],dps[chd[0]][i]+dps[chd[1]][i]-__builtin_popcount(i));
    };

  auto introduce=
    [&](int v,int add){
      base(v);

      const auto &chd=T[v].child;
      const auto &chd_bag=T[chd[0]].bag;
      const auto &pr=dps[chd[0]];

      auto &dp=dps[v];
      for(int i=0;i<(int)pr.size();i++){
        int bit=0,valid=1;
        for(int j=0;j<(int)chd_bag.size();j++){
          if((~i>>j)&1) continue;
          bit|=buff[chd_bag[j]];
          valid&=!es.count(P(chd_bag[j],add));
        }
        assert(!(bit&buff[add]));
        if(valid) chmax(dp[bit|buff[add]],pr[i]+1);
        chmax(dp[bit],pr[i]);
      }
    };

  auto forget=
    [&](int v,int rmv){
      base(v);

      const auto &chd=T[v].child;
      const auto &chd_bag=T[chd[0]].bag;
      const auto &pr=dps[chd[0]];

      auto &dp=dps[v];
      for(int i=0;i<(int)pr.size();i++){
        int bit=0;
        for(int j=0;j<(int)chd_bag.size();j++){
          if((~i>>j)&1) continue;
          if(rmv!=chd_bag[j]) bit|=buff[chd_bag[j]];
        }
        chmax(dp[bit],pr[i]);
      }
    };

  G.dfs(0,leaf,join,introduce,forget);
  auto &dp=dps[0];
  cout<<n-*max_element(dp.begin(),dp.end())<<endl;
  return 0;
}
/*
  verified 2020/02/21
  https://csacademy.com/contest/archive/task/special-mvc/statement/
*/

signed main(){
  CSA_SPECIAL_MVC();
  return 0;
}
#endif

#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T,T MOD = 1000000007>
struct Mint{
  static constexpr T mod = MOD;
  T v;
  Mint():v(0){}
  Mint(signed v):v(v){}
  Mint(long long t){v=t%MOD;if(v<0) v+=MOD;}

  Mint pow(long long k){
    Mint res(1),tmp(v);
    while(k){
      if(k&1) res*=tmp;
      tmp*=tmp;
      k>>=1;
    }
    return res;
  }

  static Mint add_identity(){return Mint(0);}
  static Mint mul_identity(){return Mint(1);}

  Mint inv(){return pow(MOD-2);}

  Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;}
  Mint& operator/=(Mint a){return (*this)*=a.inv();}

  Mint operator+(Mint a) const{return Mint(v)+=a;}
  Mint operator-(Mint a) const{return Mint(v)-=a;}
  Mint operator*(Mint a) const{return Mint(v)*=a;}
  Mint operator/(Mint a) const{return Mint(v)/=a;}

  Mint operator-() const{return v?Mint(MOD-v):Mint(v);}

  bool operator==(const Mint a)const{return v==a.v;}
  bool operator!=(const Mint a)const{return v!=a.v;}
  bool operator <(const Mint a)const{return v <a.v;}

  static Mint comb(long long n,int k){
    Mint num(1),dom(1);
    for(int i=0;i<k;i++){
      num*=Mint(n-i);
      dom*=Mint(i+1);
    }
    return num/dom;
  }
};
template<typename T,T MOD> constexpr T Mint<T, MOD>::mod;
template<typename T,T MOD>
ostream& operator<<(ostream &os,Mint<T, MOD> m){os<<m.v;return os;}
//END CUT HERE
#ifndef call_from_test

//INSERT ABOVE HERE
signed ABC127_E(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int h,w,k;
  cin>>h>>w>>k;
  using M = Mint<int>;

  M ans{0};
  for(int d=1;d<h;d++)
    ans+=M(d)*M(h-d)*M(w)*M(w);

  for(int d=1;d<w;d++)
    ans+=M(d)*M(w-d)*M(h)*M(h);

  ans*=M::comb(h*w-2,k-2);
  cout<<ans<<endl;
  return 0;
}
/*
  verified on 2019/06/12
  https://atcoder.jp/contests/abc127/tasks/abc127_e
*/

signed main(){
  //ABC127_E();
  return 0;
}
#endif

#undef call_from_test

signed main(){
  int n,m;
  while(cin>>n>>m,n){
    NiceTree G(n);
    using P = pair<int, int>;
    set<P> es;
    for(int i=0;i<n;i++){
      int j=(i+1)%n;
      G.add_edge(i,j);
      es.emplace(i,j);
      es.emplace(j,i);
    }
    for(int i=0;i<m;i++){
      int a,b;
      cin>>a>>b;
      a--;b--;
      G.add_edge(a,b);
      es.emplace(a,b);
      es.emplace(b,a);
    }
    if(n&1){
      cout<<0<<endl;
      continue;
    }
    G.build();
    auto &T=G.T;
    auto &buff=G.buff;

    using M = Mint<int, 1000003>;
    vector<vector<M>> dps(T.size());

    auto base=
      [&](int v){
        const auto &bag=T[v].bag;
        auto &dp=dps[v];
        dp.assign(1<<bag.size(),0);
      };

    auto leaf=
      [&](int v){
        base(v);
        auto &dp=dps[v];
        dp[0]=M(1);
      };

    auto join=
      [&](int v){
        base(v);
        const auto &chd=T[v].child;
        auto &dp=dps[v];

        for(int i=0;i<(int)dp.size();i++)
          for(int j=0;j<(int)dp.size();j++)
            if((i&j)==0) dp[i|j]+=dps[chd[0]][i]*dps[chd[1]][j];
      };

    auto introduce=
      [&](int v,int){
        base(v);
        const auto &chd=T[v].child;

        const auto &chd_bag=T[chd[0]].bag;
        const auto &pr=dps[chd[0]];

        auto &dp=dps[v];
        for(int i=0;i<(int)pr.size();i++){
          int bit=0;
          for(int j=0;j<(int)chd_bag.size();j++)
            if((i>>j)&1) bit|=buff[chd_bag[j]];
          dp[bit]=pr[i];
        }
      };

    auto forget=
      [&](int v,int rmv){
        base(v);
        const auto &bag=T[v].bag;
        const auto &chd=T[v].child;

        const auto &chd_bag=T[chd[0]].bag;
        const auto &pr=dps[chd[0]];

        auto &dp=dps[v];

        for(int i=0;i<(int)pr.size();i++){
          int bit=0,used=0;
          for(int j=0;j<(int)chd_bag.size();j++){
            if((~i>>j)&1) continue;
            if(rmv==chd_bag[j]) used=1;
            if(rmv!=chd_bag[j]) bit|=buff[chd_bag[j]];
          }
          if(!used){
            for(int j=0;j<(int)bag.size();j++){
              if((bit>>j)&1) continue;
              if(es.count(P(bag[j],rmv))) dp[bit|(1<<j)]+=pr[i];
            }
          }else{
            dp[bit]+=pr[i];
          }
        }
      };

    G.dfs(0,leaf,join,introduce,forget);

    auto &dp=dps[0];
    if(es.count(P(T[0].bag[0],T[0].bag[1])))
      dp.back()+=dp[0];
    cout<<dp.back()<<endl;
  }
  return 0;
}



Measured memory_bytes: 64500