#include <bits/stdc++.h>

using namespace std;

int N,K,num;
int day[101];
int a[101][4][3];

long long int dp(int d,int k,int n){
	if(n == 3)return 0;

	if(a[d][k][n] >= 0)return a[d][k][n];

	if(d == N)return a[d][k][n] = 1;

	long long int b = 0; 
	if(day[d+1] != -1){
		if(day[d+1] == k){
			b += dp(d+1, day[d+1], n+1) % 10000;
		}else{
			b += dp(d+1, day[d+1], 1) % 10000;
		}
	}else{
		for(int i = 1;i <= 3;i++){
			if(i == k){
				b += dp(d+1, i, n+1) % 10000;
			}else{
				b += dp(d+1, i, 1) % 10000;
			}
		}
	}
	return a[d][k][n] = b % 10000;
}

int main(){
	fill_n(**a,101*4*3,-1);
	fill_n(day,101,-1);
	cin >>N >> K;
	for(int i = 0;i<K;i++){
		cin >> num;
		cin >> day[num];
	}
	cout <<dp(0,0,0)<<endl; 
}