#include<cstdio>
#include<vector>
#include<utility>
#include<stack>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const long long mod=1000003;

typedef pair<int,int> P;
typedef pair<P,P> PP;

int N,M;
vector<int> G[50500];

map<PP,long long> dp;
set<PP> se;

stack<PP> st;
long long solve(){
	while(!st.empty()) st.pop();
	st.push(PP(P(0,N-1),P(0,0)));
	while(!st.empty()){
		PP pp=st.top();
		st.pop();
		if(dp.count(pp)==1) continue;
		if(se.find(pp)!=se.end()){
			int u=pp.first.first,v=pp.first.second;
			int fu=pp.second.first,fv=pp.second.second;
	//		printf("a%d %d %d %d ",u,v,fu,fv);
	//		printf("%d %d %d %d\n",u,v,fu,fv);
		/*	if(v==u+1){
				int res=(fu+fv)%2;
				res^=1;
				dp[pp]=res;
				return res;
			}*/
			long long res=0;
			int id=distance(G[u].begin(),lower_bound(G[u].begin(),G[u].end(),v));
			if(id>0&&G[u][id-1]>u){
				int w=G[u][id-1];
		//		res+=(solve(u,w,fu,1)*solve(w,v,0,fv));
				res+=dp[PP(P(u,w),P(fu,1))]*dp[PP(P(w,v),P(0,fv))];
				res%=mod;
			//	res+=(solve(u,w,fu,0)*solve(w,v,1,fv));
				res+=dp[PP(P(u,w),P(fu,0))]*dp[PP(P(w,v),P(1,fv))];
				res%=mod;
			/*	if(fu==0){
					res+=(solve(u,w,1,1)*solve(w,v,1,fv));
					res%=mod;
				}*/
				if(fu==0&&fv==0&&binary_search(G[u].begin(),G[u].end(),v)){
				//	res+=(solve(u,w,1,0)*solve(w,v,1,1));
				//	res+=(solve(u,w,1,1)*solve(w,v,0,1));
					res+=dp[PP(P(u,w),P(1,0))]*dp[PP(P(w,v),P(1,1))];
					res+=dp[PP(P(u,w),P(1,1))]*dp[PP(P(w,v),P(0,1))];
					res%=mod;
				}
			}else{
				int u=pp.first.first,v=pp.first.second;
				int fu=pp.second.first,fv=pp.second.second;
				//res+=solve(u+1,v,fu^1,fv);
				res+=dp[PP(P(u+1,v),P(fu^1,fv))];
				if(fu==0&&fv==0&&binary_search(G[u].begin(),G[u].end(),v)){
					//res+=solve(u+1,v,0,1);
					res+=dp[PP(P(u+1,v),P(0,1))];
				}
				res%=mod;
			}
		//	printf("%lld\n",res);
			dp[pp]=res;
		}
		else{
			int u=pp.first.first,v=pp.first.second;
			int fu=pp.second.first,fv=pp.second.second;
		//	printf("b%d %d %d %d\n",u,v,fu,fv);
			if(v==u+1){
				int res=(fu+fv)%2;
				res^=1;
				dp[pp]=res;
				continue;
			}
			se.insert(pp);
			st.push(pp);
			int id=distance(G[u].begin(),lower_bound(G[u].begin(),G[u].end(),v));
			if(id>0&&G[u][id-1]>u){
				int w=G[u][id-1];
				for(int a=0;a<2;a++) for(int b=0;b<2;b++){
					st.push(PP(P(u,w),P(a,b)));
					st.push(PP(P(w,v),P(a,b)));
				}
			}
			else{
				for(int a=0;a<2;a++) for(int b=0;b<2;b++){
					st.push(PP(P(u+1,v),P(a,b)));
				}
			}
		}
	}
	return dp[PP(P(0,N-1),P(0,0))];
}

void init(){
	map<PP,long long> mp;
	swap(mp,dp);
	set<PP> se_;
	swap(se,se_);
	for(int i=0;i<N;i++) G[i].clear();
}

void output(){
	map<PP,long long>::iterator it=dp.begin();
	for(;it!=dp.end();it++){
		PP pp=it->first;
		long long val=it->second;
		printf("%d %d %d %d =%lld\n",pp.first.first,pp.first.second,pp.second.first,pp.second.second,
		val);
	}
}

int main(){
	while(true){
		init();
		scanf("%d%d",&N,&M);
		if(N==0) break;
		for(int i=0;i<M;i++){
			int u,v;
			scanf("%d%d",&u,&v);
			u--;v--;
			G[u].push_back(v);
			G[v].push_back(u);
		}
		G[0].push_back(N-1);
		G[N-1].push_back(0);
		for(int i=0;i<N;i++) sort(G[i].begin(),G[i].end());
		long long ans=solve();
		ans+=mod;
		ans%=mod;
	//	output();
		printf("%lld\n",ans);
	}
	return 0;
}

Measured memory_bytes: 37740