#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#include<queue>

using namespace std;


int N, K;
int plan[1000];
int dp[1000][3][3];

int solve(int now, int yest, int ends) {
	if (ends >= 3) return 0;
	if (now == N) return 1;

	if (dp[now][yest][ends] != -1) return dp[now][yest][ends];

	if (plan[now] != -1) {
		if(plan[now] != yest) dp[now][yest][ends] = solve(now + 1, plan[now], 1);
		else dp[now][yest][ends] = solve(now + 1, plan[now], ends+1);
	}
	else {
		dp[now][yest][ends] = solve(now + 1, yest, ends + 1) + solve(now + 1, (yest+1)%3, 1) + solve(now + 1, (yest+2)%3, 1);
	}

	dp[now][yest][ends] %= 10000;

	return dp[now][yest][ends];
}

int main() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		plan[i] = -1;
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				dp[i][j][k] = -1;
			}
		}
	}
	for (int i = 0; i < K; i++) {
		int a, b;
		cin >> a >> b;
		plan[a-1] = b-1;
	}

	cout << solve(0, 0, 0) << endl;

	return 0;
}

/*
int N, K;
int cost[100][100];
int sum[100][100];
vector<int> can[100];
queue<int> que;
int S, G;
bool ok;

void solve(int now) {
	for (int i = 0; i < can[now].size(); i++) {
		if (sum[S][can[now][i]] > sum[S][now] + cost[now][can[now][i]]) {
			sum[S][can[now][i]] = sum[S][now] + cost[now][can[now][i]];

			if (can[now][i] != G) que.push(can[now][i]);
			else ok = true;
		}
	}
}

int main() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cost[i][j] = 99999999999;
		}
	}

	for (int i = 0; i < K; i++) {
		int type;
		cin >> type;
		if (type == 0) {
			cin >> S >> G;
			S--; G--;
			ok = false;

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					sum[i][j] = 99999999999;
				}
			}

			sum[S][S] = 0;
			que.push(S);
			while (!que.empty())
			{
				solve(que.front());
				que.pop();
			}

			if (ok == true) cout << sum[S][G] << endl;
			else cout << -1 << endl;
		}
		else {
			int c, d, e;
			cin >> c >> d >> e;
			c--; d--;
			if (cost[c][d] > e) {
				cost[c][d] = e;
				cost[d][c] = e;

				can[c].push_back(d);
				can[d].push_back(c);
			}
		}
	}

	return 0;
}
*/

/*
int main() {
	int M, N;
	pair<int, int> star[210], sky[1010];
	star[0] = make_pair(0, 0);

	cin >> M;
	for (int i = 1; i <= M; i++) {
		cin >> star[i].first >> star[i].second;
		star[i].first -= star[i - 1].first;
		star[i].second -= star[i - 1].second;
	}

	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> sky[i].first >> sky[i].second;
	}

	bool tmp = true;
	for (int i = 1; i <= M; i++) {
		for (int j = 1; j <= M && tmp == true; j++) {
			for (int k = 1; k <= N && tmp == true; k++) {
				if (sky[i].first + star[k].first == sky[j].first && sky[i].second + star[k].second == sky[j].second) {
					break;
				}
				else if (k == N) {
					tmp = false;
				}
			}
		}
	}


	return 0;
}
*/

/*
int a, b, N;
bool stop[20][20];
int dp[20][20];

int solve(int x, int y) {
	if (x == a - 1 && y == b - 1) return 1;
	if (stop[x][y] == true) return 0;

	if (dp[x][y] != -1) return dp[x][y];

	dp[x][y] = solve(x, y + 1) + solve(x + 1, y);
	return dp[x][y];
}

int main() {
	while (true)
	{
		cin >> a >> b;
		if (a == 0) break;

		for (int i = 0; i < a; i++) {
			for (int j = 0; j < b; j++) {
				stop[i][j] = false;
				dp[i][j] = -1;
			}
		}

		cin >> N;
		for (int i = 0; i < N; i++) {
			int x, y;
			cin >> x >> y;
			stop[x - 1][y - 1] = true;
		}

		cout << solve(0, 0) << endl;

	}
	
	return 0;
}
*/

/*
int a, b, c, N;
int Ans[1000];
int tmps[100][100][100];
int main() {
while (true) {
cin >> a >> b >> c;
if (a == 0) break;
cin >> N;

for (int i = 0; i < (a + b + c); i++) {
Ans[i] = 2;
}
for (int i = 0; i < a; i++)
for (int j = 0; j < b; j++)
for (int k = 0; k < c; k++)
tmps[i][j][k] = -1;

for (int i = 0; i < N; i++) {
int ti, tj, tk, tr;
cin >> ti >> tj >> tk >> tr;
tj -= a;
tk -= (a + b);
tmps[ti - 1][tj - 1][tk - 1] = tr;
}

for (int i = 0; i < a; i++) {
for (int j = 0; j < b; j++) {
for (int k = 0; k < c; k++) {
if (tmps[i][j][k] == 1) {
Ans[i] = 1;
Ans[j + a] = 1;
Ans[k + a + b] = 1;
}
}
}
}

for (int i = 0; i < a; i++) {
for (int j = 0; j < b; j++) {
for (int k = 0; k < c; k++) {
if (tmps[i][j][k] == 0) {
if (Ans[i] == 1 && Ans[a + j] == 1) {
Ans[a + b + k] = 0;
}
else if (Ans[a + j] == 1 && Ans[a + b + k] == 1) {
Ans[i] = 0;
}
else if (Ans[i] == 1 && Ans[a + b + k] == 1) {
Ans[a + j] = 0;
}
}
}
}
}

for (int i = 0; i < a + b + c; i++) {
cout << Ans[i] << endl;
}

}

return 0;
}
*/

/*
int main() {
int N;
string name;
int ans = 0;

cin >> N >> name;

string word;
for (int i = 0; i < N; i++) {
cin >> word;

vector<int> first, second;
for (int j = 0; j < word.size(); j++) {
if (name[0] == word[j]) {
first.push_back(j);
}
}
for (int j = 0; j < word.size(); j++) {
if (name[1] == word[j]) {
second.push_back(j);
}
}

bool judge = true;
for (int j = 0; j < first.size() && judge == true; j++) {
for (int k = 0; k < second.size() && judge == true; k++) {
if (first[j] < second[k]) {
int tmp = first[j];
for (int l = 0; l < name.size() && tmp < word.size(); l++) {
if (word[tmp] != name[l]) {
break;
}
else if (l == name.size() - 1) {
ans++;
judge = false;
}
tmp += second[k] - first[j];
}
}
}
}
}

cout << ans << endl;

return 0;
}
*/
/*
int main() {
int N, K;
cin >> N >> K;

for (int i = 0; i < K; i++) {
int a, b;
cin >> a >> b;

if (a > N / 2) {
a = N - a + 1;
}
if (b > N / 2) {
b = N - b + 1;
}

int tmp = min(a, b);

tmp = tmp % 3;
if (tmp == 0) tmp = 3;

cout << tmp << endl;
}

return 0;
}
*/

/*
//パーティー
int main() {
int N, M;
cin >> N >> M;
bool Friends[500][500] = {};
bool already[500] = {};
already[0] = true;

for (int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
a--;
b--;
Friends[a][b] = true;
Friends[b][a] = true;
}

int ans = 0;
for (int i = 0; i < N; i++) {
if (Friends[0][i] == true) {
if (already[i] == false) {
ans++;
already[i] = true;
}
for (int j = 0; j < N; j++) {
if (Friends[i][j] == true && already[j] == false) {
already[j] = true;
ans++;
}
}
}
}

cout << ans << endl;

return 0;
}
*/

/*
//カードゲーム
int main() {
int N;
cin >> N;
int TaroSize = N;
int HanaSize = N;

int Taro[210];
for (int i = 1; i <= 2 * N; i++) {
Taro[i] = -1;
}

for (int i = 0; i < N; i++) {
int tmp;
cin >> tmp;
Taro[tmp] = 1;
}

bool TaroTurn = true;
int Now = 0;
while (TaroSize != 0 && HanaSize != 0) {
if (TaroTurn) {
for (int i = Now + 1; i <= 2 * N; i++) {
if (Taro[i] == 1) {
Now = i;
Taro[i] = 0;
TaroSize--;
TaroTurn = false;
if (Now == 2 * N) {
Now = 0;
TaroTurn = true;
}
break;
}
else if (i >= 2 * N - 1) {
Now = 0;
TaroTurn = false;
}
}
}
else {
for (int i = Now + 1; i <= 2 * N; i++) {
if (Taro[i] == -1) {
Now = i;
Taro[i] = 0;
HanaSize--;
TaroTurn = true;
if (Now == 2 * N) {
Now = 0;
TaroTurn = false;
}
break;
}
if (i >= 2 * N) {
Now = 0;
TaroTurn = true;
}
}
}
}

cout << HanaSize << endl;
cout << TaroSize << endl;


return 0;
}
*/



Measured memory_bytes: 3100