#include <cstdio>
using namespace std;

int dp[101][4][4];
int schedule[101];

int main()
{
	int N, K;
	
	scanf("%d %d", &N, &K);
	
	for (int i = 0; i < K; i++){
		int A, B;
		scanf("%d %d", &A, &B);	
		schedule[A] = B;
	}
	
	dp[0][0][0] = 1;
	
	for (int i = 0; i < N; i++){
		for (int j = 0; j < 4; j++){
			for (int k = 0; k < 4; k++){
				for (int l = 1; l < 4; l++){
					if (!(j == k && k == l) && (schedule[i + 1] == 0 || schedule[i + 1] == l)){
						dp[i + 1][k][l] = (dp[i + 1][k][l] + dp[i][j][k]) % 10000;
						
						//printf("%d\n", dp[i + 1][k][l]);
					}
				}
			}
		}
	}
	
	int cnt = 0;
	
	for (int i = 1; i < 4; i++){
		for (int j = 1; j < 4; j++){
			cnt = (cnt + dp[N][i][j]) % 10000;
		}
	}
	
	printf("%d\n", cnt);
	
	return 0;
}