#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <climits>
using namespace std;
typedef long long int ll;

ll mod=10000;

ll dp[111][5][5];
int a[111];

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n,k; cin >> n >> k;
	for(int i=0;i<k;i++){
		int x,y; cin >> x >> y;
		a[x]=y;
	}
	dp[0][3][3]=1;
	for(int i=0;i<n;i++){
		for(int j=0;j<4;j++){
			for(int p=0;p<4;p++){
				if(dp[i][j][p]==0)continue;
				if(a[i+1]!=0){
					if(a[i+1]==j+1&&a[i+1]==p+1)continue;
					if(1){
						(dp[i+1][a[i+1]-1][j]+=dp[i][j][p])%=mod;
					}
				}
				else{
					if(j==p){
						for(int h=0;h<3;h++){
							if(p==h)continue;
							(dp[i+1][h][j]+=dp[i][j][p])%=mod;
						}
					}
					else{
						for(int h=0;h<3;h++){
							(dp[i+1][h][j]+=dp[i][j][p])%=mod;
						}
					}
				}
			}
		}
	}
	ll ans=0;
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			//cout << i << " " << j << " " << dp[n-1][i][j] << endl;
			ans+=dp[n][i][j];
		}
	}
	cout << ans%mod << endl;
}
