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 <cstring>
using namespace std;

#define MOD 10000

int n, m;
int t[102];
int dp[102][4][4];

void solve(){
  memset(dp, 0, sizeof(dp));
  dp[0][3][3] = 1;

  for(int i = 0; i < n; i++){
    for(int pre1 = 0; pre1 < 4; pre1++){
      for(int pre2 = 0; pre2 < 4; pre2++){
        if(dp[i][pre1][pre2] == 0) continue;

        if(t[i] != -1){
          if(pre1 == pre2 && pre2 == t[i]) continue;
          dp[i + 1][pre2][t[i]] += dp[i][pre1][pre2];
          dp[i + 1][pre2][t[i]] %= MOD;
        }
        else{
          for(int today = 0; today < 3; today++){
            if(pre1 == pre2 && pre2 == today) continue;
            dp[i + 1][pre2][today] += dp[i][pre1][pre2];
            dp[i + 1][pre2][today] %= MOD;
          }
        }
      }
    }
  }

  int ans = 0;

  for(int i = 0; i < 3; i++){
    for(int j = 0; j < 3; j++){
      ans += dp[n][i][j];
      ans %= MOD;
    }
  }

  cout << ans << endl;
}

int main(){
  while(cin >> n >> m){
    memset(t, -1, sizeof(t));

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

    solve();
  }
}

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 "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;
}

C++: #include<bits/stdc++.h>
using namespace std;
int main(){
  int n,t,p[110]={},dp[102][4][4]={};
  cin>>n>>t;
  for(int i=0;i<t;i++){
    int a,b;
    cin>>a>>b;
    p[a]=b;
  }
   
  if(p[1]&&p[2])dp[3][p[2]][p[1]]=1;
  else if(p[2])for(int i=1;i<4;i++)dp[3][p[2]][i]=1;
  else if(p[1])for(int i=1;i<4;i++)dp[3][i][p[1]]=1;
  else
    for(int i=1;i<4;i++)
      for(int j=1;j<4;j++)dp[3][i][j]=1;
 
  for(int i=3;i<=n;i++)
    for(int j=1;j<4;j++) //1
      for(int k=1;k<4;k++){//2
    if(p[i]==j&&j==k)continue;
    if(p[i])dp[i+1][p[i]][j]=(dp[i+1][p[i]][j]+dp[i][j][k])%10000;
    else
      for(int l=1;l<4;l++){
        if(j==k&&k==l)continue;
        dp[i+1][l][j]=(dp[i+1][l][j]+dp[i][j][k])%10000;
      }
      }
  int ans=0;
  for(int i=1;i<4;i++)
    for(int j=1;j<4;j++)ans+=dp[n+1][i][j];
  cout<<ans%10000<<endl;
  return 0;
}