#include <iostream>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

int main() {
	int n, k;
	int s[101][3] = {};
	int b[101] = {};
	cin >> n >> k;
	REP(i, k) {
		int a;
		cin >> a;
		cin >> b[a];
	}
	s[0][0] = 1;
	FOR(i, 1, n+1) {
		REP(j, 3) {
			if(b[i]>0 && b[i]!=j+1) {
				s[i][j] = 0;
			}else {
				if(i==1 || i==2) {
					REP(k, 3) s[i][j] += s[i-1][k];
				} else if(i==3) {
					REP(k, 3) s[i][j] += s[i-1][k];
					if((b[i-1]==0 || b[i-1]==j+1) && (b[i-2]==0 || b[i-2]==j+1))s[i][j] -= 1;
				} else {
					REP(k, 3) s[i][j] += s[i-1][k];
					s[i][j] -= s[i-1][j];
					if(b[i-1]==0 || b[i-1]==j+1) {
						REP(k, 3) s[i][j] += s[i-2][k];
						s[i][j] -= s[i-2][j];
					}
				}
			}
			s[i][j] += 10000;
			s[i][j] %= 10000;
		}
	}
	
	int r = 0;
	REP(i, 3)r += s[n][i];
	r %= 10000;
	
	cout << r << endl;
	
	return 0;
}