//#include <bits/stdc++.h>
#define _CRT_SECURE_NO_WARNINGS
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>
#include <cmath>
#endif


using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define FORR(i,a,b) for(int i=(b)-1; i>=(a); i--)

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

template<typename T>
void fillall(T& arr, const T& value) {
	arr = value;
}
template<typename T, typename ARR>
void fillall(ARR& arr, const T& value) {
	for (auto& i : arr) fillall(i, value);
}

#define MOD 1000003

int n, m;
pii es[52525];
int deg[52525];

vi g[52525];

const int M = 65536;
unordered_map<int, int> memo;
ll f(int l, int r) {
	//if(l+1==r)return 0;
	while (!(l + 2 >= r) && g[l].empty()) {
		l += 2;
	}
	while (!(l + 2 >= r) && g[r-1].empty()) {
		r -= 2;
	}
	if (l + 2 >= r)return 1;
	if (memo.count(l * M + r))return memo[l * M + r];
	ll ans = 0;
	auto gbeg = std::upper_bound(g[l].begin(), g[l].end(), l);
	auto gend = std::lower_bound(g[l].begin(), g[l].end(), r);

	//if (gend - gbeg >= 1) {
	//	int lst = gend[-1];
	//	if (gend[-1] == r - 1) {
	//		ans += f(l+1, r - 1);
	//		ans %= MOD;
	//		if (gend - gbeg >= 2) {
	//			ans += (f(l, gend[-2] + 1) * f(gend[-2] + 1, r)) % MOD;
	//			ans %= MOD;
	//		}
	//		else {
	//			ans += f(l + 2, r);
	//			ans %= MOD;
	//		}
	//	}
	//	else {
	//		ans += (f(l, lst + 1) * f(lst + 1, r)) % MOD;
	//		ans %= MOD;
	//	}
	//}
	//else {
	//	ans += f(l + 2, r);
	//	ans %= MOD;
	//}
	ans += f(l + 2, r);
	if (gend - gbeg >= 2) {
		int fst = gbeg[0];
		int lst = gend[-1];
		ll bef = f(l + 1, fst);
		ll aft = f(lst + 1, r);    // O(f(r-lst))
		// printf("bef=%lld, aft=%lld\n",bef,aft);
		// f(l+1, *)
		// f(*, lst)
		FOR(i, 0, (gend - gbeg)) {
			int to = gbeg[i];
			ans += bef * f(fst, to) * f(to + 1, lst + 1) % MOD * aft % MOD;
			ans %= MOD;
		}
	}
	else if ((gend - gbeg) == 1) {
		// int to = gg.back();
		//for (int to : gg) {
		//}
		int to = gbeg[0];
		ans += f(l + 1, to) * f(to + 1, r);
		ans %= MOD;
	}
	else {
		// do nothing
	}
	// printf("[%d, %d) -> %lld\n",l,r,ans);
	//return ans;
	return memo[l * M + r] = ans;
}
ll solve(int n) {
	memo.clear();
	return f(0, n);
}

int main() {
	int ccc = 1;
	while (true) {
		scanf("%d%d", &n, &m);
		if (n + m == 0)break;
		fill(deg, deg + n, 0);
		REP(i, m) {
			int a, b;
			scanf("%d%d", &a, &b);
			--a; --b;
			es[i] = pii(a, b);
			deg[a]++; deg[b]++;
		}
		if (n % 2 == 1) {
			puts("0");
			continue;
		}
		int id = -1;
		REP(i, n)if (deg[i] == 0) {
			id = i;
			// cerr << id << endl;
			break;
		}
		// id - (id+1)
		// (id+2) -> 0
		REP(i, n)g[i].clear();
		REP(i, m) {
			int a = es[i].first, b = es[i].second;
			if (a == id || b == id)continue;
			if (a == id + 1 || b == id + 1)continue;
			a = (a - (id + 2) + n + n) % n;
			b = (b - (id + 2) + n + n) % n;
			if (a % 2 == b % 2)continue;
			//if (a > b)swap(a, b);
			g[b].push_back(a);
			g[a].push_back(b);
		}
		REP(i, n)sort(g[i].begin(), g[i].end());
		ll ans = solve(n - 2);
		// cerr << "first : " << ans << endl;
		// (id-1) - id
		// (id+1) -> 0
		REP(i, n)g[i].clear();
		REP(i, m) {
			int a = es[i].first, b = es[i].second;
			if (a == id || b == id)continue;
			if (a == id - 1 || b == id - 1)continue;
			a = (a - (id + 1) + n + n) % n;
			b = (b - (id + 1) + n + n) % n;
			if (a % 2 == b % 2)continue;
			//if (a > b)swap(a, b);
			g[b].push_back(a);
			g[a].push_back(b);
		}
		REP(i, n)sort(g[i].begin(), g[i].end());
		int x = solve(n - 2);
		ans += x;
		// cerr << "second : " << x << endl;
		ans %= MOD;
		printf("%lld\n", ans);
		// fprintf(stderr, "%d/141: %lld\n",ccc++,ans);
	}
	return 0;
}


Measured memory_bytes: 11484