#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <unordered_map>
using namespace std;

int N, K;
vector<int> plan;
vector<vector<vector<int > > > dp;

int solve(int day, int today, int tommorow) {
	if (dp[day][today][tommorow] != -1) return dp[day][today][tommorow];
	if (day == N - 2)return 1;
	int tmp = 0;
	dp[day][today][tommorow] = 0;
	for (int i = 0; i < 3; i++) {
		if ((plan[day + 2] != -1 && plan[day + 2] != i) || (today == tommorow && tommorow == i))continue;
		dp[day][today][tommorow] += solve(day + 1, tommorow, i);
	}
	if (dp[day][today][tommorow] > 10000)dp[day][today][tommorow] %= 10000;
	return dp[day][today][tommorow];
}

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

	int ans = 0;
	for (int i = 0; i < 3; i++){
		if (plan[0] != -1 && plan[0] != i)continue;
		for (int j = 0; j < 3; j++) {
			if (plan[1] != -1 && plan[1] != j)continue;
			ans += solve(0, i, j);
		}
	}

	if (ans > 10000)ans %= 10000;
	cout << ans << endl;
	return 0;
}
