Go: package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

var scanner = bufio.NewScanner(os.Stdin)

// 文字列を1行取得
func StrStdin() (stringReturned string) {
//	scanner := bufio.NewScanner(os.Stdin)

	scanner.Scan()
	stringInput := scanner.Text()

	stringReturned = strings.TrimSpace(stringInput)
	return
}

// 整数値1つ取得
func IntStdin() (int, error) {
	stringInput := StrStdin()
	return strconv.Atoi(strings.TrimSpace(stringInput))
}

// 空白や空文字だけの値を除去したSplit()
func SplitWithoutEmpty(stringTargeted string, delim string) (stringReturned []string) {
	stringSplited := strings.Split(stringTargeted, delim)

	for _, str := range stringSplited {
		if str != "" {
			stringReturned = append(stringReturned, str)
		}
	}

	return
}

// デリミタで分割して文字列スライスを取得
func SplitStrStdin(delim string) (stringReturned []string) {
	// 文字列で1行取得
	stringInput := StrStdin()

	// 空白で分割
	// stringSplited := strings.Split(stringInput, delim)
	stringReturned = SplitWithoutEmpty(stringInput, delim)

	return
}

// デリミタで分割して整数値スライスを取得
func SplitIntStdin(delim string) (intSlices []int, err error) {
	// 文字列スライスを取得
	stringSplited := SplitStrStdin(" ")

	// 整数スライスに保存
	for i := range stringSplited {
		var iparam int
		iparam, err = strconv.Atoi(stringSplited[i])
		if err != nil {
			return
		}
		intSlices = append(intSlices, iparam)
	}
	return
}

func main() {
	nk, _ := SplitIntStdin(" ")
	n, k := nk[0], nk[1]
	kind := make([]int, n)
	for i := 0; i < k; i++ {
		var tmp []int
		var err error
		if tmp, err = SplitIntStdin(" "); err != nil {
			panic(err)
		}
		kind[tmp[0]-1] = tmp[1]
	}
	dp := make([][3][3]int, n)
	if kind[0] > 0 {
		dp[0][0][kind[0]-1] = 1
	} else {
		for i := 0; i < 3; i++ {
			dp[0][0][i] = 1
		}
	}
	if kind[1] > 0 {
		for i := 0; i < 3; i++ {
			dp[1][i][kind[1]-1] = dp[0][0][i]
		}
	} else {
		for i := 0; i < 3; i++ {
			for j := 0; j < 3; j++ {
				dp[1][i][j] = dp[0][0][i]
			}
		}
	}
	for i := 1; i < n-1; i++ {
		if kind[i+1] > 0 {
			for j := 0; j < 3; j++ {
				if j == kind[i+1]-1 {
					for k := 0; k < 3; k++ {
						if j != k {
							dp[i+1][j][kind[i+1]-1] += dp[i][k][j]
							dp[i+1][j][kind[i+1]-1] %= 10000
						}
					}
				} else {
					for k := 0; k < 3; k++ {
						dp[i+1][j][kind[i+1]-1] += dp[i][k][j]
						dp[i+1][j][kind[i+1]-1] %= 10000
					}
				}
			}
		} else {
			for j := 0; j < 3; j++ {
				for k := 0; k < 3; k++ {
					for l := 0; l < 3; l++ {
						if j != k || k != l {
							dp[i+1][k][j] += dp[i][l][k]
							dp[i+1][k][j] %= 10000
						}
					}
				}
			}
		}
	}
	result := 0
	for i := 0; i < 3; i++ {
		for j := 0; j < 3; j++ {
			result += dp[n-1][i][j]
		}
	}
	// fmt.Println(dp)
	// fmt.Println(kind)
	fmt.Println(result % 10000)
}

C++: #include "bits/stdc++.h"

using namespace std;

//#define int long long

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define FORR(i, a, b) for (int i = (a); i >= (b); i--)

#define pb push_back
#define VDEL(v, n) v.erase(v.begin() + (n))
#define ALL(v) v.begin(), v.end()

#define INTMAX 2147483647
#define INF 200000000
#define TINT(str) atoi(str.c_str())
#define TSTR(num) to_string(num)

typedef long long ll;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<vector<int>> VII;

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

//the end of library zone

// i i-1 pas i-2 pas
int dp[110][3][3];

int res[110];

int dn(int a)
{
    a -= 1;
    if(a == -1)
    {
        a = 2;
    }
    return a;
}

signed main()
{
    REP(i, 110)
    {
        res[i] = -1;
    }

    int N, K;
    cin >> N >> K;

    REP(i, K)
    {
        int A, B;
        cin >> A >> B;
        res[A - 1] = B - 1;
    }

    if(res[0] != -1)
    {
        dp[0][res[0]][dn(res[0])] = 1;
    }
    else
    {
        dp[0][0][1] = 1;
        dp[0][1][2] = 1;
        dp[0][2][0] = 1;
    }

    FOR(i, 1, N)
    {
        REP(h1, 3)
        REP(h2, 3)
        {
            if(res[i] != -1)
            {
                if(!(h1 == h2 && h1 == res[i]))
                {
                    dp[i][res[i]][h1] += 
                        dp[i - 1][h1][h2];
                    dp[i][res[i]][h1] %= 10000;
                }
            }
            else
            {
                REP(tdy, 3)
                {
                    if(!(h1 == h2 && h1 == tdy))
                    {
                        dp[i][tdy][h1] += 
                            dp[i - 1][h1][h2];
                        dp[i][tdy][h1] %= 10000;
                    }
                }
            }
        }
    }

    int ans = 0;
    REP(h1, 3)
    REP(h2, 3)
    {
        ans += dp[N - 1][h1][h2];
    }
    ans %= 10000;

    cout << ans << endl;

    return 0;
}

C++: #include <cstdio>

#define INF 1

int dp[3][3][101];

int main() {
    int i;
    int n, k;
    int d[3][2] = {{1,2}, {2,0}, {0,1}};
    int sum = 0;

    scanf("%d %d", &n, &k);

    for (i=0;i<=n;i++) {
        int j;
        for (j=0;j<3;j++) {
            dp[0][j][i] = 0;
            dp[1][j][i] = 0;
            dp[2][j][i] = 0;
        }
    }
    dp[0][0][1] = 1;
    dp[1][0][1] = 1;
    dp[2][0][1] = 1;

    for (i=0;i<k;i++) {
       int j;
       int a, b;

       scanf("%d %d", &a, &b);

       for (j=0;j<3;j++) {
           dp[d[b-1][0]][j][a] = -INF;
           dp[d[b-1][1]][j][a] = -INF;
       }
    }


    for (i=1;i<=n;i++) {
       int j;
       for (j=0;j<3;j++) {
          if (dp[j][0][i] == -INF || ((dp[d[j][0]][0][i-1] < 0) && (dp[d[j][0]][1][i-1] < 0) && (dp[d[j][1]][0][i-1] < 0) && (dp[d[j][1]][1][i-1] < 0))) {
              dp[j][0][i] = -INF;
          } else {
              if (dp[d[j][0]][0][i-1] >= 0) dp[j][0][i] += dp[d[j][0]][0][i-1];
              if (dp[d[j][0]][1][i-1] >= 0) dp[j][0][i] += dp[d[j][0]][1][i-1];
              if (dp[d[j][1]][0][i-1] >= 0) dp[j][0][i] += dp[d[j][1]][0][i-1];
              if (dp[d[j][1]][1][i-1] >= 0) dp[j][0][i] += dp[d[j][1]][1][i-1];
          }
          if (dp[j][0][i] != -INF) dp[j][0][i] %= 10000;
          
          if (dp[j][1][i] == -INF || dp[j][0][i-1] < 0) {
              dp[j][1][i] = -INF;
          } else {
              dp[j][1][i] += dp[j][0][i-1];
          }

          if (dp[j][1][i] != -INF) dp[j][1][i] %= 10000;
       }
    }

    for (i=0;i<3;i++) {
        int j;
        for (j=0;j<3;j++) {
            if (dp[i][j][n] > 0) sum += dp[i][j][n];
            sum %= 10000;
        }
    }

    printf("%d\n", sum);
}

C++: #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][3][3];

LL dp(LL d, LL b2, LL b1)
{
	if (memo[d][b2][b1] != -1) { return memo[d][b2][b1]; }
	if (d == N) { 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(0, 0, 0) << std::endl;
	return 0;
}