#include <iostream>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
int test[101];
int main() {
	long long n, k, a, b; cin >> n >> k;
	map<string, int>usi;
	usi["itiiti"] = 0; usi["itini"] = 0; usi["itisan"] = 0;
	usi["niiti"] = 0; usi["nini"] = 0; usi["nisan"] = 0;
	usi["saniti"] = 0; usi["sanni"] = 0; usi["sansan"] = 0;
	map<string, int>uma;
	uma["itiiti"] = 0; uma["itini"] = 0; uma["itisan"] = 0;
	uma["niiti"] = 0; uma["nini"] = 0; uma["nisan"] = 0;
	uma["saniti"] = 0; uma["sanni"] = 0; uma["sansan"] = 0;
	for (int h = 0; h < k; h++) {
		cin >> a >> b; test[a] = b;
	}
	if (test[1] != 0 && test[2] != 0) {
		if (test[1] == 1 && test[2] == 1) { usi["itiiti"] = 1; uma["itiiti"] = 1; }
		if (test[1] == 1 && test[2] == 2) { usi["itini"] = 1; uma["itini"] = 1; }
		if (test[1] == 1 && test[2] == 3) { usi["itisan"] = 1; uma["itisan"] = 1; }
		if (test[1] == 2 && test[2] == 1) { usi["niiti"] = 1; uma["niiti"] = 1; }
		if (test[1] == 2 && test[2] == 2) { usi["nini"] = 1; uma["nini"] = 1; }
		if (test[1] == 2 && test[2] == 3) { usi["nisan"] = 1; uma["nisan"] = 1; }
		if (test[1] == 3 && test[2] == 1) { usi["saniti"] = 1; uma["saniti"] = 1; }
		if (test[1] == 3 && test[2] == 2) { usi["sanni"] = 1; uma["sanni"] = 1; }
		if (test[1] == 3 && test[2] == 3) { usi["sansan"] = 1; uma["sansan"] = 1; }
	}
	else if (test[1] != 0 && test[2] == 0) {
		if (test[1] == 1) {
			usi["itiiti"] = 1; usi["itini"] = 1; usi["itisan"] = 1;
			uma["itiiti"] = 1; uma["itini"] = 1; uma["itisan"] = 1;
		}
		if (test[1] == 2) {
			usi["niiti"] = 1; usi["nini"] = 1; usi["nisan"] = 1;
			uma["niiti"] = 1; uma["nini"] = 1; uma["nisan"] = 1;
		}
		if (test[1] == 3) {
			usi["saniti"] = 1; usi["sanni"] = 1; usi["sansan"] = 1;
			uma["saniti"] = 1; uma["sanni"] = 1; uma["sansan"] = 1;
		}
	}
	else if (test[1] == 0 && test[2] != 0) {
		if (test[2] == 1) {
			usi["itiiti"] = 1; usi["niiti"] = 1; usi["saniti"] = 1;
			uma["itiiti"] = 1; uma["niiti"] = 1; uma["saniti"] = 1;
		}
		if (test[2] == 2) {
			usi["itini"] = 1; usi["nini"] = 1; usi["sanni"] = 1;
			uma["itini"] = 1; uma["nini"] = 1; uma["sanni"] = 1;
		}
		if (test[2] == 3) {
			usi["itisan"] = 1; usi["nisan"] = 1; usi["sansan"] = 1;
			uma["itisan"] = 1; uma["nisan"] = 1; uma["sansan"] = 1;
		}
	}
	else {
		usi["itiiti"] = 1; usi["itini"] = 1; usi["itisan"] = 1;
		usi["niiti"] = 1; usi["nini"] = 1; usi["nisan"] = 1;
		usi["saniti"] = 1; usi["sanni"] = 1; usi["sansan"] = 1;
		uma["itiiti"] = 1; uma["itini"] = 1; uma["itisan"] = 1;
		uma["niiti"] = 1; uma["nini"] = 1; uma["nisan"] = 1;
		uma["saniti"] = 1; uma["sanni"] = 1; uma["sansan"] = 1;
	}
	for (int h = 3; h <= n; h++) {
		if (h % 2 == 0) {
			if (test[h] == 1) {
				usi["itiiti"] = (uma["niiti"] + uma["saniti"]) % 10000;
				usi["niiti"] = (uma["itini"] + uma["nini"] + uma["sanni"]) % 10000;
				usi["saniti"] = (uma["itisan"] + uma["nisan"] + uma["sansan"]) % 10000;
				usi["itini"] = 0; usi["itisan"] = 0; usi["nini"] = 0;
				usi["nisan"] = 0; usi["sanni"] = 0; usi["sansan"] = 0;
			}
			else if (test[h] == 2) {
				usi["itini"] = (uma["itiiti"] + uma["niiti"] + uma["saniti"]) % 10000;
				usi["nini"] = (uma["itini"] + uma["sanni"]) % 10000;
				usi["sanni"] = (uma["itisan"] + uma["nisan"] + uma["sansan"]) % 10000;
				usi["itiiti"] = 0; usi["itisan"] = 0; usi["niiti"] = 0;
				usi["nisan"] = 0; usi["saniti"] = 0; usi["sansan"] = 0;
			}
			else if (test[h] == 3) {
				usi["itisan"] = (uma["itiiti"] + uma["niiti"] + uma["saniti"]) % 10000;
				usi["nisan"] = (uma["itini"] + uma["nini"] + uma["sanni"]) % 10000;
				usi["sansan"] = (uma["itisan"] + uma["nisan"]) % 10000;
				usi["itini"] = 0; usi["itiiti"] = 0; usi["nini"] = 0;
				usi["niiti"] = 0; usi["sanni"] = 0; usi["saniti"] = 0;
			}
			else {
				usi["itiiti"] = (uma["niiti"] + uma["saniti"]) % 10000;
				usi["itini"] = (uma["itiiti"] + uma["niiti"] + uma["saniti"]) % 10000;
				usi["itisan"] = (uma["itiiti"] + uma["niiti"] + uma["saniti"]) % 10000;
				usi["niiti"] = (uma["itini"] + uma["nini"] + uma["sanni"]) % 10000;
				usi["nini"] = (uma["itini"] + uma["sanni"]) % 10000;
				usi["nisan"] = (uma["itini"] + uma["nini"] + uma["sanni"]) % 10000;
				usi["saniti"] = (uma["itisan"] + uma["nisan"] + uma["sansan"]) % 10000;
				usi["sanni"] = (uma["itisan"] + uma["nisan"] + uma["sansan"]) % 10000;
				usi["sansan"] = (uma["itisan"] + uma["nisan"]) % 10000;
			}
		}
		else {
			if (test[h] == 1) {
				uma["itiiti"] = (usi["niiti"] + usi["saniti"]) % 10000;
				uma["niiti"] = (usi["itini"] + usi["nini"] + usi["sanni"]) % 10000;
				uma["saniti"] = (usi["itisan"] + usi["nisan"] + usi["sansan"]) % 10000;
				uma["itini"] = 0; uma["itisan"] = 0; uma["nini"] = 0;
				uma["nisan"] = 0; uma["sanni"] = 0; uma["sansan"] = 0;
			}
			else if (test[h] == 2) {
				uma["itini"] = (usi["itiiti"] + usi["niiti"] + usi["saniti"]) % 10000;
				uma["nini"] = (usi["itini"] + usi["sanni"]) % 10000;
				uma["sanni"] = (usi["itisan"] + usi["nisan"] + usi["sansan"]) % 10000;
				uma["itiiti"] = 0; uma["itisan"] = 0; uma["niiti"] = 0;
				uma["nisan"] = 0; uma["saniti"] = 0; uma["sansan"] = 0;
			}
			else if (test[h] == 3) {
				uma["itisan"] = (usi["itiiti"] + usi["niiti"] + usi["saniti"]) % 10000;
				uma["nisan"] = (usi["itini"] + usi["nini"] + usi["sanni"]) % 10000;
				uma["sansan"] = (usi["itisan"] + usi["nisan"]) % 10000;
				uma["itini"] = 0; uma["itiiti"] = 0; uma["nini"] = 0;
				uma["niiti"] = 0; uma["sanni"] = 0; uma["saniti"] = 0;
			}
			else {
				uma["itiiti"] = (usi["niiti"] + usi["saniti"]) % 10000;
				uma["itini"] = (usi["itiiti"] + usi["niiti"] + usi["saniti"]) % 10000;
				uma["itisan"] = (usi["itiiti"] + usi["niiti"] + usi["saniti"]) % 10000;
				uma["niiti"] = (usi["itini"] + usi["nini"] + usi["sanni"]) % 10000;
				uma["nini"] = (usi["itini"] + usi["sanni"]) % 10000;
				uma["nisan"] = (usi["itini"] + usi["nini"] + usi["sanni"]) % 10000;
				uma["saniti"] = (usi["itisan"] + usi["nisan"] + usi["sansan"]) % 10000;
				uma["sanni"] = (usi["itisan"] + usi["nisan"] + usi["sansan"]) % 10000;
				uma["sansan"] = (usi["itisan"] + usi["nisan"]) % 10000;
			}
		}
	}
	int ans = 0;
	if (n % 2 == 1) {
		ans += uma["itiiti"] + uma["itini"] + uma["itisan"] + uma["niiti"] + uma["nini"];
		ans += uma["nisan"] + uma["saniti"] + uma["sanni"] + uma["sansan"];
	}
	else {
		ans += usi["itiiti"] + usi["itini"] + usi["itisan"] + usi["niiti"] + usi["nini"];
		ans += usi["nisan"] + usi["saniti"] + usi["sanni"] + usi["sansan"];
	}
	cout << ans % 10000 << endl;
	cin >> n;
}


Measured memory_bytes: 3240