#include <iostream>
using namespace std;
const int MOD = 10000;
int memo[4][4][105] = {};
int schedule[105] = {};
int N, K;
int calc(int dby, int yesterday, int today){
	if (today == N) return 1;
	if (memo[dby][yesterday][today] > 0) return memo[dby][yesterday][today];

	if (schedule[today] != 0){
		if (dby == yesterday && yesterday == schedule[today]) return 0;
		return calc(yesterday, schedule[today], today + 1);
	}

	int ans = 0;
	for (int i = 1; i <= 3; i++){
		if (dby == yesterday && yesterday == i) continue;
		ans = (ans + calc(yesterday, i, today + 1)) % MOD;
	}
	memo[dby][yesterday][today] = ans;
	return ans;
}
int main(){
	cin >> N >> K;
	for (int i = 0; i < K; i++){
		int A, B;
		cin >> A >> B;
		schedule[A-1] = B;
	}
	cout << calc(0, 0, 0) << endl;
	return 0;
}