#include <stdio.h>
#include <algorithm>
#include <string.h>
#define DAY_MAX	123
#define PASTA_MAX	5
#define ONAZI_MAX	123

int max;


int set_pasta[DAY_MAX];
int memo[DAY_MAX][PASTA_MAX][ONAZI_MAX];

int dp(int day, int pasta, int onazi){
	int numbuf = 0;
	int ans = 0;
	if (memo[day][pasta][onazi] >= 0) return memo[day][pasta][onazi];
	if (onazi == 3) return 0;
	if (day == max - 1) return 1;
	if (set_pasta[day + 1] >= 1){
		if (set_pasta[day + 1] == pasta) return memo[day][pasta][onazi] = dp(day + 1, pasta, onazi + 1);
		else return memo[day][pasta][onazi] = dp(day + 1, set_pasta[day + 1], 1);
	}
	else{
		for (int a = 0; a < 3; a++){
			if (a + 1 == pasta) ans += dp(day + 1, pasta, onazi + 1);
			else ans += dp(day + 1, a + 1, 1);
			ans %= 10000;
		}
		return ans;
	}
}

int main(){
	int num;
	int buf;
	int answer = 0;
	memset(memo, 255, sizeof(memo));
	scanf("%d%d", &max, &num);
	for (int a = 0; a < num; a++){
		scanf("%d", &buf);
		scanf("%d", &set_pasta[buf - 1]);
	}
	if (set_pasta[0] >= 1) printf("%d\n", dp(0, set_pasta[0], 1));
	else printf("%d\n", (dp(0, 1, 1) + dp(0, 2, 1) + dp(0, 3, 1)) % 10000);
	return 0;
}