#include <iostream>
#include <vector>
using namespace std;

int N, K, A, B;

int dfs(vector< vector< vector<int> > >& dp,vector<bool>& dec, vector<int>& pasta,int pppasta,int ppasta,int n)
{
	if (n == N + 1)
		return 1;
	if (dp[pppasta][ppasta][n] != -1) {
		return dp[pppasta][ppasta][n];
	}
	dp[pppasta][ppasta][n] = 0;
	if (dec[n]) {
		if (n - 2 >= 0 && pppasta == ppasta && ppasta == pasta[n])
			return 0;
		else
			return dp[pppasta][ppasta][n] = dfs(dp, dec, pasta, ppasta, pasta[n], n + 1);
	}
	for (int i = 1; i <= 3; i++) {
		pasta[n] = i;
		if (n - 2 >= 0 && pppasta == ppasta && ppasta == pasta[n])
			continue;
		dp[pppasta][ppasta][n] += dfs(dp, dec, pasta, ppasta, pasta[n], n + 1);
	}
	dp[pppasta][ppasta][n] %= 10000;
	return dp[pppasta][ppasta][n];
}

int main()
{
	cin >> N >> K;
	vector<bool> dec(N + 1, false);
	vector<int> pasta(N + 1, 0);
	vector< vector< vector<int> > > dp(4, vector< vector<int> >(4, vector<int>(N + 1, -1)));
	for (int i = 0; i < K; i++) {
		cin >> A >> B;
		dec[A] = true;
		pasta[A] = B;
	}
	cout << dfs(dp, dec, pasta, 0, 0, 1) << endl;
	return 0;
}