#include <iostream>
#define MOD 10000;
using namespace std;

int yotei[100] = {};
int dp[100][6] = {};

int n,k;

int main() {
    cin >> n >> k;
    for(int i = 0; i < k; i++) {
        int a,b;
        cin >> a >> b;
        a--;
        yotei[a] = b;
    }
    // 0day
    for(int i = 0; i < 3; i++) dp[0][i] += (yotei[0]==i||yotei[0]==0)?1:0;
    // 1day...
    for(int i = 1; i < n; i++) {
        if(yotei[i]==0||(yotei[i]%3==0)) dp[i][0] = dp[i-1][1]+dp[i-1][2]+dp[i-1][4]+dp[i-1][5];
        if(yotei[i]==0||(yotei[i]%3==1)) dp[i][1] = dp[i-1][0]+dp[i-1][2]+dp[i-1][3]+dp[i-1][5];
        if(yotei[i]==0||(yotei[i]%3==2)) dp[i][2] = dp[i-1][0]+dp[i-1][1]+dp[i-1][3]+dp[i-1][4];
        if(yotei[i]==0||(yotei[i]%3==0)) dp[i][3] = dp[i-1][0];
        if(yotei[i]==0||(yotei[i]%3==1)) dp[i][4] = dp[i-1][1];
        if(yotei[i]==0||(yotei[i]%3==2)) dp[i][5] = dp[i-1][2];
        for(int j = 0; j < 6; j++) dp[i][j] %= MOD;
    }
    int ans = 0;
    for(int i = 0; i < 6; i++) {
        ans = (ans+dp[n-1][i])%MOD;
    }
    cout << ans << endl;
}
