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 <iostream>
#include <numeric>
#include <vector>

template <class T>
std::vector<T> vec(int len, T elem) { return std::vector<T>(len, elem); }

constexpr int MOD = 10000;

void solve() {
    int n, k;
    std::cin >> n >> k;

    std::vector<int> xs(n, 0);
    while (k--) {
        int i, x;
        std::cin >> i >> x;
        xs[--i] = x;
    }

    auto dp = vec(4, vec(4, 0));
    dp[0][0] = 1;
    auto ndp = dp;

    for (auto x : xs) {
        for (auto& v : ndp) {
            std::fill(v.begin(), v.end(), 0);
        }

        for (int px1 = 0; px1 <= 3; ++px1) {
            for (int px2 = 0; px2 <= 3; ++px2) {
                for (int nx = 1; nx <= 3; ++nx) {
                    if (x != 0 && x != nx) continue;
                    if (px1 != 0 && px1 == px2 && px2 == nx) continue;

                    (ndp[px2][nx] += dp[px1][px2]) %= MOD;
                }
            }
        }

        std::swap(dp, ndp);
    }

    int ans = 0;
    for (const auto& v : dp) {
        (ans += std::accumulate(v.begin(), v.end(), 0)) %= MOD;
    }

    std::cout << ans << std::endl;
}

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    solve();

    return 0;
}

C++: #include<iostream>
using namespace std;
int dp[105][3][2],a[105],n,m,p,q;
int main(){
	cin>>n>>m;for(int i=0;i<m;i++){cin>>p>>q;a[p]=q;}
	dp[1][0][0]=1;dp[1][1][0]=1;dp[1][2][0]=1;
	for(int i=2;i<=n;i++){
		if(a[i]==0 || a[i]==1){
			dp[i][0][0]+=(dp[i-1][1][0]+dp[i-1][1][1]+dp[i-1][2][0]+dp[i-1][2][1]);dp[i][0][0]%=10000;
			dp[i][0][1]+=dp[i-1][0][0];dp[i][0][1]%=10000;
		}
		if(a[i]==0 || a[i]==2){
			dp[i][1][0]+=(dp[i-1][0][0]+dp[i-1][0][1]+dp[i-1][2][0]+dp[i-1][2][1]);dp[i][1][0]%=10000;
			dp[i][1][1]+=dp[i-1][1][0];dp[i][1][1]%=10000;
		}
		if(a[i]==0 || a[i]==3){
			dp[i][2][0]+=(dp[i-1][0][0]+dp[i-1][0][1]+dp[i-1][1][0]+dp[i-1][1][1]);dp[i][2][0]%=10000;
			dp[i][2][1]+=dp[i-1][2][0];dp[i][2][1]%=10000;
		}
	}
	cout<<(dp[n][0][0]+dp[n][0][1]+dp[n][1][0]+dp[n][1][1]+dp[n][2][0]+dp[n][2][1])%10000<<endl;
	return 0;
}

C++: #include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 100;
int N, K;
int plan[MAX_N + 1];
int memo[MAX_N + 1][4][4];
int solve(int n, int b1, int b2){
	if(n == N+1) return 1;
	if(memo[n][b1][b2] != -1) return memo[n][b1][b2];
	if(plan[n] != 0){
		if(b1 == b2 && b1 == plan[n])
			return 0;
		else
			return solve(n+1, plan[n], b1)%10000;
	}
	int t=0;
	for(int i=1; i<=3; ++i){
		if(b1==b2 && b1==i ) continue;
		t+=solve(n+1, i, b1)%10000;
	}
	return memo[n][b1][b2] = t%10000;
}
int main(){
	scanf("%d %d", &N, &K);
	for(int i=0; i<K; ++i){
		int d, k;
		scanf("%d %d", &d, &k);
		plan[d] = k;
	}
	for(int i=0; i<=N; ++i)
		for(int j=0; j<4; ++j)
			for(int k=0; k<4; ++k)
				memo[i][j][k] = -1;
	printf("%d\n", solve(1, 0, 0));
	return 0;
}

C++: #include <iostream>
using namespace std;

int main(){
	int n, k, a, b, ans = 0, pasta[101] = {}, dp[101][4][4] = {};
	
	cin >> n >> k;
	for(int i = 0; i < k; i++){
		cin >> a >> b;
		pasta[a] = b;
	}
	
	for(int i = 1; i <= 3; i++){
		if(pasta[1] > 0 && i != pasta[1]){
			continue;
		}
		dp[1][1][i] = 1;
	}
	
	for(int i = 2; i <= n; i++){
		for(int j = 1; j <= 3; j++){
			for(int l = 1; l <= 3; l++){
				if(pasta[i] > 0 && l != pasta[i]){
					continue;
				}
	
				dp[i][j][l] = dp[i - 1][1][j] + dp[i - 1][2][j] + dp[i - 1][3][j];

				if(i > 2 && j == l && dp[i][j][l] > 0 && dp[i - 1][j][l] > 0){
					dp[i][j][l] -= dp[i - 1][j][l];
				}
	
				dp[i][j][l] %= 10000;
			}
		}
	}
	
	for(int j = 1; j <= 3; j++){
		for(int l = 1; l <= 3; l++){
			ans += dp[n][j][l];
		}
	}
	
	cout << ans % 10000 << endl;
	
	return 0;
}

C++: #include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define REP(i,j) for(int i=0;i<j;i++)
int dp[1000][4][4];int yotei[101][3]={{0},{0}};
const int INF=454354643;
	int n,k;
	
	int dfs(int day,int now,int mae){
		if(dp[day][now][mae]!=0)return dp[day][now][mae];
		if(day==n){return 1;}
		int sum=0;
		if(yotei[day+1][1]==1||yotei[day+1][2]==1||yotei[day+1][3]==1){
			for(int i=1;i<=3;i++){
				if(yotei[day+1][i]==1){
					if(mae!=i||now!=i){
						sum+=dfs(day+1,i,now);
					}
					else now= 0;
				}
			}
		}
		else {
		if(mae!=1||now!=1&&yotei[day+1][1]!=1)sum+=dfs(day+1,1,now);
		if(mae!=2||now!=2&&yotei[day+1][2]!=1)sum+=dfs(day+1,2,now);
		if(mae!=3||now!=3&&yotei[day+1][3]!=1)sum+=dfs(day+1,3,now);
		}
		return dp[day][now][mae]=sum%10000;
	}
	
int main(){
	cin>>n>>k;
	REP(i,1000)REP(j,4)REP(k,4)dp[i][j][k]=0;
	for(int i=0;i<k;i++){
		int a,b;
		cin>>a>>b;
		yotei[a][b]=1;
	}
	cout<<dfs(0,0,0)%10000<<endl;
	return 0;
}