#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>

#define rep(i, n) for(int i = 0; i < (n); i++)

using namespace std;

const int MOD = 10000;
int dp[101][4][4];
int pasta[101];
int main(){
	int n, k;
	cin >> n >> k;
	rep(i, k){
		int d, p;
		cin >> d >> p;
		pasta[d] = p;
	}
	
	dp[0][0][0] = 1;
	for(int i = 1; i <= n; i++){
		for(int l = 1; l < 4; l++){
			if(pasta[i] && pasta[i] != l) continue;
			for(int j = 0; j < 4; j++){
				for(int k = 0; k < 4; k++){
					if(l == j && j == k) continue;
					dp[i][l][j] += dp[i-1][j][k];
					dp[i][l][j] %= MOD;
				}
			}
		}
	}
	int ans = 0;
	rep(i, 4) rep(j, 4) ans += dp[n][i][j];
	cout << ans%MOD << endl;

	return 0;
}