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>

using namespace std;

int main()
{
    int N,K;

    cin >> N >> K;

    int dp[3][3][N];
    int menu[N];

    for(int i=0; i<N; ++i) {
        menu[i]=-1;
    }

    for(int i=0; i<K; ++i) {
        int a,b;
        cin >> a >> b;
        menu[a-1]=b-1;
    }

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

    if(menu[0]!=-1 && menu[1]!=-1) {
        dp[menu[0]][menu[1]][1]=1;
    } else if(menu[0]!=-1) {
        dp[menu[0]][0][1]=1;
        dp[menu[0]][1][1]=1;
        dp[menu[0]][2][1]=1;
    } else if(menu[1]!=-1) {
        dp[0][menu[1]][1]=1;
        dp[1][menu[1]][1]=1;
        dp[2][menu[1]][1]=1;
    } else {
        for(int i=0; i<3; ++i) {
            for(int j=0; j<3; ++j) {
                dp[i][j][1]=1;
            }
        }
    }

    for(int d=2; d<N; ++d) {
        if(menu[d]!=-1) {
            for(int i=0; i<3; ++i) {
                for(int j=0; j<3; ++j) {
                    if(j!=menu[d]) {
                        dp[i][j][d]=0;
                    } else {
                        dp[i][j][d]=dp[0][i][d-1]+dp[1][i][d-1]+dp[2][i][d-1];
                        if(i==j) dp[i][j][d]+=10000-dp[i][i][d-1];
                        dp[i][j][d]%=10000;
                    }
                }
            }
        } else {
            for(int i=0; i<3; ++i) {
                for(int j=0; j<3; ++j) {
                    dp[i][j][d]=dp[0][i][d-1]+dp[1][i][d-1]+dp[2][i][d-1];
                    if(i==j) dp[i][j][d]+=10000-dp[i][i][d-1];
                    dp[i][j][d]%=10000;
                }
            }
        }
    }

    int ans=0;

    for(int i=0; i<3; ++i) {
        for(int j=0; j<3; ++j) {
            ans+=dp[i][j][N-1];
            ans%=10000;
        }
    }

    cout << ans << endl;


    return 0;
}

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

int dp[110][4][4];
int N,M;

int pas[110];

int main(){
		 
	
  cin >> N >> M;
  memset(pas,0,sizeof(pas));	 
  memset(dp,0,sizeof(dp));

  for(int i = 0; i < M; i++){
    int x,y;
    cin >> x >> y;
    pas[x] = y;
  }

  if(pas[1] == 0){
    for(int j = 0; j <= 3; j++){
      dp[1][j][1] = 1;
    }
  }
  else{
    dp[1][pas[1]][1] = 1;
  }


  for(int i = 2; i <= N; i++){
 
    if(pas[i] == 0){ //その日が決まってないなら
      for(int j = 1; j <= 3; j++){
	// k = 2
	if(pas[i+1] == j) //次の日が決まっててアウト
	  dp[i][j][2] = 0;
	else{
	  dp[i][j][2] += dp[i-1][j][1];
	  dp[i][j][2] %= 10000;
	}
	// k = 1
	for(int t = 1; t <= 3; t++){
	  if(j != t){
	    dp[i][j][1] += dp[i-1][t][1] + dp[i-1][t][2];
	    dp[i][j][1] %= 10000;
	  }
	}
 
	//	if( j == pas[i+1] && j == pas[i+2]) dp[i][j][1] = 0;	
      }
    }
    
    if(pas[i] != 0){ //決まってる
      for(int j = 1; j <= 3; j++){
	if(pas[i] != j){
	  dp[i][pas[i]][1] += dp[i-1][j][1] + dp[i-1][j][2];
	  dp[i][pas[i]][1] %= 10000;
	}
      }

      dp[i][pas[i]][2] += dp[i-1][pas[i]][1];
      dp[i][pas[i]][2] %= 10000;	   
	
    }
    for(int j = 1; j <=3 ;j++){
      for(int k = 1; k <= 2; k++){
	//	cout << dp[i][j][k] << " ";
      }
      //      cout << endl;
    }
    //    cout << endl;
  }



  int ans=0;
  for(int j =1; j <= 3;j++){
    for(int k = 1; k <=2 ;k++){
      ans += dp[N][j][k];
      ans %= 10000;
    }
  }
  cout << ans << endl;

  
  return 0;
}

C++: #include <iostream>
using namespace std;
const int MOD = 10000;
int memo[4][4][105] = {};
int schedule[105] = {};
int N, K;
int calc(int dby, int yesterday, int today){
	if (today == N) return 1;
	if (memo[dby][yesterday][today] > 0) return memo[dby][yesterday][today];

	if (schedule[today] != 0){
		if (dby == yesterday && yesterday == schedule[today]) return 0;
		return calc(yesterday, schedule[today], today + 1);
	}

	int ans = 0;
	for (int i = 1; i <= 3; i++){
		if (dby == yesterday && yesterday == i) continue;
		ans = (ans + calc(yesterday, i, today + 1)) % MOD;
	}
	memo[dby][yesterday][today] = ans;
	return ans;
}
int main(){
	cin >> N >> K;
	for (int i = 0; i < K; i++){
		int A, B;
		cin >> A >> B;
		schedule[A-1] = B;
	}
	cout << calc(0, 0, 0) << endl;
	return 0;
}