#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define sz size()
#define fs first
#define sc second
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<unsigned short> vs;

typedef vector< pair<vi,vs> > TD;
//first: child of tree, second: bag

const ll mod = 1e6+3;

/*Tree Decomposition for a graph with small treewidth.*/
inline TD heuristic_tree_decomposition(vector<vs> &g, set<ui> is_edge){
  unsigned int n = g.size();
  TD res = TD(n);
  vi use(n,-1), deg(n);

  priority_queue<pii> q;
  rep(i,n){
    deg[i] = g[i].sz; deg[i]*=-1;
    q.push(pii(deg[i],i));
  }

  int id = n-1;
  while(q.sz){
    int v = q.top().sc, d = q.top().fs; q.pop();
    if(use[v]!=-1 || deg[v] != d)continue;

    vs unuse;
    for(int u : g[v]){
      if(use[u]==-1)unuse.push_back(u);
      else if(use[u]>=0){
	res[id].first.push_back(use[u]);
	use[u] = -2;
      }
    }

    res[id].second.push_back(v);
    for(int a : unuse){
      res[id].second.push_back(a);
      deg[a]++;
      for(int b :unuse){
	ui aa = a, bb = b;
	if(aa>bb)swap(aa,bb);
	if(aa!=bb && !is_edge.count(aa*n + bb)){
	  g[aa].pb(bb);
	  g[bb].pb(aa);
	  is_edge.insert(aa*n + bb);
	  deg[aa]--; deg[bb]--;
	}
      }
    }
    for(int u: unuse)q.push(pii(deg[u],u));

    use[v] = id;
    id--;
  }

  return res;
}

inline void toNice(TD &t, int id){
  stack<int> s;
  s.push(id);

  while(s.sz){
    id = s.top(); s.pop();
    
    //for join
    while(t[id].first.size()>2){
      vi child(2);
      child[0] = t[id].first.back(); t[id].first.pop_back();
      child[1] = t[id].first.back(); t[id].first.pop_back();
      t.push_back(make_pair(child, t[id].second));
      t[id].first.push_back(t.size()-1);
    }

    if(t[id].first.size()==2){
      rep(i,2){
	const int &j = t[id].first[i];
	if(t[id].second != t[j].second){
	  vi child(1);
	  child[0] = j;
	  t.push_back(make_pair(child, t[id].second));
	  t[id].first[i] = t.size()-1;
	}
      }
    }

    //for introduce & forget
    if(t[id].first.size()==1){
      const int &j = t[id].first[0];
      vi child(1);
      child[0] = j;
      
      vi disA, disB;
      rep(a,t[id].second.size()){
	bool f = true;
	rep(b,t[j].second.size()){
	  if(t[id].second[a] == t[j].second[b])f = false;
	}
	if(f)disA.push_back(a);
      }
      rep(b,t[j].second.size()){
	bool f = true;
	rep(a,t[id].second.size()){
	  if(t[id].second[a] == t[j].second[b])f = false;
	}
	if(f)disB.push_back(b);
      }
      
      if(disA.size() + disB.size() > 1){
	if(disA.size()>0){
	  vs tmp = t[id].second;
	  tmp.erase(tmp.begin() + disA[0]);
	  t.push_back(make_pair(child, tmp));
	  t[id].first[0] = t.size()-1;
	}else{
	  vs tmp = t[id].second;
	  tmp.push_back(t[j].second[disB[0]]);
	  t.push_back(make_pair(child, tmp));
	  t[id].first[0] = t.size()-1;
	}      
      }
    }
    
    //for leaf
    if(t[id].first.size() == 0){
      if(t[id].second.size() > 1){
	vs tmp;
	rep(i,t[id].second.size()-1)tmp.push_back(t[id].second[i]);
	t.push_back(make_pair(vi(), tmp));
	t[id].first.push_back(t.size()-1);
      }
    }

    rep(i,t[id].first.size()){
      s.push(t[id].first[i]);
    }
  }
}

inline int dp(int id, int use, unsigned int n,
	      const TD &t, const set<ui> &is_edge, unordered_map<int,int> &memo){
  int key = 100*id + use;

  int maxs = 0;
  vector<int> s(t.sz);
  int pos = 0;
  s[pos++] = key;

  while(pos){
    ll res = 0;
    key = s[--pos];
    id = key/100; use = key%100;
    const vi &child = t[id].fs;
    const vs &bag = t[id].sc;
    
    //for leaf
    if(child.sz==0){
      memo[key] = use;
      goto END;
    }
    
    if(child.sz==1){
      const vs &nbag = t[child[0]].second;
      vi to_bag(nbag.size(),-1), to_nbag(bag.size(),-1);
      rep(i,bag.size())rep(j,nbag.size()){
	if(bag[i] == nbag[j]){
	  to_bag[j] = i; to_nbag[i] = j;
	}
      }
      
      //for introduce
      if(nbag.sz < bag.sz){
	int nuse = 0;
	rep(i,bag.sz){
	  if(to_nbag[i]<0){
	    if( ((use>>i)&1) == 0 ){
	      memo[key] = 0;
	      goto END;
	    }
	  }else{
	    if( ((use>>i)&1) )nuse |= 1<<to_nbag[i];
	  }
	}
	int nxt = child[0]*100 + nuse;
	if(memo.count(nxt)){
	  memo[key] = memo[nxt];
	  goto END;
	}else{
	  s[pos++] = key; s[pos++] = nxt;
	  goto END;
	}
      }
      
      //for forget
      if(nbag.sz > bag.sz){
	int add = -1,  nuse = 0;
	rep(i,nbag.sz){
	  if(to_bag[i]<0)add = i;
	  else if( (use>>to_bag[i])&1 )nuse |= 1<<i;
	}
	
	ll res = 0;
	int nxt = child[0]*100 + nuse;
	if(memo.count(nxt)){
	  (res += memo[nxt]) %= mod;
	}else{
	  s[pos++] = key; s[pos++] = nxt;
	  goto END;
	}

	rep(i,bag.sz){
	  if((use>>i)&1)continue;
	  
	  ui a = bag[i], b = nbag[add];
	  if(a>b)swap(a,b);
	  if(is_edge.count(a*n + b)){
	    nxt = child[0]*100 + (nuse | (1<<add) | (1<<to_nbag[i]));
	    if(memo.count(nxt)){
	      (res += memo[nxt]) %= mod;
	    }else{
	      s[pos++] = key; s[pos++] = nxt;
	      goto END;
	    }
	  }
	}
	memo[key] = res;
      }
    }
    
    //for join
    if(child.sz==2){
      int n = bag.sz, unuse = (1<<n)-1 - use, sub = unuse;
      do{
	int nxt1 = child[0]*100 + (use|sub), nxt2 = child[1]*100 + (use|(unuse-sub));
	if(memo.count(nxt1) == 0){
	  s[pos++] = key; s[pos++] = nxt1;
	  goto END;
	}
	if(memo[nxt1]){
	  if(memo.count(nxt2) == 0){
	    s[pos++] = key; s[pos++] = nxt2;
	    goto END;
	  }
	  if(memo[nxt2]){
	    res += (ll)memo[nxt1] * memo[nxt2];
	    res %= mod;
	  }
	}
	sub = (sub-1)&unuse;
      }while(sub != unuse);
    
      memo[key] = res;
    }
  END: maxs = max(maxs, (int)s.sz);
  }
  return memo[key];
}

int main(){
  ui n,m,a,b;
  while(scanf("%d%d",&n,&m),n){
    vector<vs> g(n);
    set<ui> is_edge;

    rep(i,n){
      a = i, b = (i+1)%n;
      g[a].pb(b);
      g[b].pb(a);
      if(a<b)is_edge.insert(a*n + b);
      else is_edge.insert(b*n + a);
    }
    rep(i,m){
      scanf("%d%d",&a,&b); a--; b--;
      g[a].pb(b);
      g[b].pb(a);
      if(a<b)is_edge.insert(a*n + b);
      else is_edge.insert(b*n + a);
    }

    TD t = heuristic_tree_decomposition(g,is_edge);
    g.clear();
    toNice(t,0);

    ll res = 0;
    unordered_map<int,int> memo;

    int x = t[0].sc.sz;
    int match = x*(x-1)/2;
    rep(bit,1<<match){
      int use = 0;
      rep(i,match){
	if( (bit>>i)&1 ){
	  a = i, b = (i+1)%x;
	  if(is_edge.count(t[0].fs[a]*mod + t[0].fs[b])){
	    if( (use>>a)&1 || (use>>b)&1 ){
	      use = -1; break;
	    }else{
	      use |= 1<<a | 1<<b;
	    }
	  }else{
	    use = -1; break;
	  }
	}
      }
      if(use<0)continue;
      res += dp(0,use,n,t,is_edge,memo);
      res %= mod;
    }
    printf("%lld\n",res);
  }
}

Measured memory_bytes: 62812