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

using i64 = int64_t;

constexpr i64 MOD = 10000;

i64 dp[102][4][4]={0};

int main(){
    int n, k;
    cin >> n >> k;
    vector<pair<int, int>> v;
    for(int i=0;i<k;++i){
        int a, b;
        cin >> a >> b;
        v.emplace_back(a, b);
    }
    sort(v.begin(), v.end());
    dp[0][0][0] = 1;
    int d = 0;
    for(int i=1;i<=n;++i){
        for(int j=0;j<4;++j){
            for(int k=0;k<4;++k){
                if(v[d].first == i){
                    if(j == k && k == v[d].second)continue;
                    dp[i][k][v[d].second] += dp[i-1][j][k];
                    dp[i][k][v[d].second] %= MOD;
                }else{
                    for(int l=1;l<4;++l){
                        if(j == k && k == l)continue;
                        dp[i][k][l] += dp[i-1][j][k];
                        dp[i][k][l] %= MOD;
                    }
                }
            }
        }
        if(v[d].first == i)d++;
    }

    i64 ans = 0;
    for(int i=1;i<4;++i){
        for(int j=1;j<4;++j){
            ans += dp[n][i][j];
            ans %= MOD;
        }
    }

    cout << ans << endl;

    return 0;
}

