#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
//#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define MOD 1000003
#define NUM 50005

enum Type{
	NOT_NOT,
	NOT_USED,
	USED_NOT,
	USED_USED,
};

struct Info{
	Info(){

		left = right = 0;
	}
	Info(int arg_left,int arg_right){
		left = arg_left;
		right = arg_right;
	}
	bool operator<(const struct Info &arg) const{

		if(left != arg.left){

			return left < arg.left;
		}else{

			return right < arg.right;
		}
	}

	int left,right;
};

int V,E;
map<Info,ll> dp[4];
vector<int> G[NUM];


ll recursive(int left,int right,bool used_0,bool used_1){

	if(left+1 == right){

		if(used_0 == true && used_1 == true){

			return true;
		}else{

			return false;
		}
	}

	bool used[2];

	used[0] = used_0;
	used[1] = used_1;

	Type type;

	if(used[0] == true && used[1] == true){

		type = USED_USED;

	}else if(used[0] == true && used[1] == false){

		type = USED_NOT;

	}else if(used[0] == false && used[1] == true){

		type = NOT_USED;

	}else if(used[0] == false && used[1] == false){

		type = NOT_NOT;
	}

	Info info;
	info.left = left;
	info.right = right;

	if(dp[type].count(info) > 0){

		return dp[type][info];
	}

	ll ret = 0;

	int L,R,mid,next_node;

	L = 0,R = G[right].size()-1,mid = (L+R)/2;

	while(L <= R){

		if(G[right][mid] > left){

			next_node = G[right][mid];
			R = mid-1;

		}else{

			L = mid+1;
		}
		mid = (L+R)/2;
	}

	ret += recursive(next_node,right,true,used[1])*recursive(left,next_node,used[0],false);
	ret %= MOD;

	ret += recursive(next_node,right,false,used[1])*recursive(left,next_node,used[0],true);
	ret %= MOD;

	bool is_adj[2];

	L = 0,R = G[left].size()-1,mid = (L+R)/2;
	is_adj[0] = false;

	while(L <= R){

		if(G[left][mid] == next_node){

			is_adj[0] = true;
			break;
		}else if(G[left][mid] > next_node){

			R = mid-1;
		}else{

			L = mid+1;
		}

		mid = (L+R)/2;
	}

	L = 0,R = G[right].size()-1,mid = (L+R)/2;
	is_adj[1] = false;

	while(L <= R){

		if(G[right][mid] == next_node){

			is_adj[1] = true;
			break;
		}else if(G[right][mid] > next_node){

			R = mid-1;
		}else{

			L = mid+1;
		}

		mid = (L+R)/2;
	}

	if(used[0] == false && is_adj[0] == true){

		ret += recursive(next_node,right,true,used[1])*recursive(left,next_node,true,true);
		ret %= MOD;
	}

	if(used[1] == false && is_adj[1] == true){

		ret += recursive(next_node,right,true,true)*recursive(left,next_node,used[0],true);
		ret %= MOD;
	}

	return dp[type][info] = ret%MOD;
}


void func(){

	for(int i = 0; i < V; i++){

		G[i].clear();
	}

	for(int i = 0; i < 4; i++){

		dp[i].clear();
	}

	int from,to;

	for(int i = 0; i <= V-1; i++){

		from = i;
		to = (i+1)%V;

		G[from].push_back(to);
		G[to].push_back(from);
	}

	for(int i = 0; i < E; i++){

		scanf("%d %d",&from,&to);
		from--;
		to--;

		G[from].push_back(to);
		G[to].push_back(from);
	}

	for(int i = 0; i < V; i++){

		sort(G[i].begin(),G[i].end());
	}

	ll ans = recursive(0,V-1,true,true)+recursive(0,V-1,false,false);

	printf("%lld\n",ans%MOD);
}


int main(){

	while(true){

		scanf("%d %d",&V,&E);
		if(V == 0 && E == 0)break;

		func();
	}

	return 0;
}



Measured memory_bytes: 25908