#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

const LL mod = 10000;
LL N, K, A[112], B[112];
std::map<LL, LL>list;
LL memo[112][4][4];

LL dp(LL d, LL b2, LL b1)
{
	if (memo[d][b2][b1] != -1) { return memo[d][b2][b1]; }
	if (d == N + 1) { return memo[d][b2][b1] = 1; }
	if (list[d] > 0)
	{
		if (!(b2 == b1 && b1 == list[d])) { return memo[d][b2][b1] = dp(d + 1, b1, list[d]) % mod; }
		else { return memo[d][b2][b1] = 0; }
	}
	else
	{
		LL res = 0;
		for (int i = 1; i <= 3; ++i)
		{
			if (!(b2 == b1 && b1 == i)) { res += dp(d + 1, b1, i) % mod; }
			res %= mod;
		}
		return memo[d][b2][b1] = res;
	}
}

int main()
{
	memset(memo, -1, sizeof(memo));
	in >> N >> K;
	rep(i, N) { in >> A[i] >> B[i]; }
	rep(i, N) { list[A[i]] = B[i]; }
	out << dp(1, 0, 0) << std::endl;
	return 0;
}