#include<bits/stdc++.h>
using namespace std;

const int mod=10000;
int N,K;
int order[100];

int memo[100][4][4];
int calc(int day=0,int prev=0,int cur=0){
    if(day==N)return 1;
    if(~memo[day][prev][cur])return memo[day][prev][cur];

    int ret=0;
    for(int i=1;i<=3;i++){
        if(order[day]&&order[day]!=i)continue;
        if(prev==cur&&cur==i)continue;
        ret=(ret+calc(day+1,cur,i))%mod;
    }
    return memo[day][prev][cur]=ret;
}

int main(){
    cin>>N>>K;
    for(int i=0;i<K;i++){
        int a,b;
        cin>>a>>b;
        order[--a]=b;
    }

    memset(memo,-1,sizeof(memo));
    cout<<calc()<<endl;
    return 0;
}