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 <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define ALL(v) (v).begin(), (v).end()
#define LENGTHOF(x) (sizeof(x) / sizeof(*(x)))
#define AFILL(a, b) fill((int*)a, (int*)(a + LENGTHOF(a)), b)
#define SQ(x) ((x)*(x))
#define Mod(x, mod) (((x)+(mod)%(mod))
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define INF 1 << 30
#define EPS 1e-10
#define MOD 1000000007

typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;

int N, K;
int day[128];
int dp[128][4][4];

int dfs(int n, int pprev, int prev){
  if(n==N) return 1;
  int &res = dp[n][pprev][prev];
  if(res >= 0) return res;
  res = 0;
  if(day[n]){
    if(day[n]!=pprev || day[n]!=prev) res = (res+dfs(n+1, prev, day[n]))%10000;
  }else{
    for(int i=1;i<=3;i++){
      if(i==pprev && i==prev) continue;
      res = (res+dfs(n+1, prev, i))%10000;
    }
  }
  return res;
}

int main(){
  scanf("%d%d", &N, &K);
  memset(day, 0, sizeof(day));
  memset(dp, -1, sizeof(dp));
  int A, B;
  rep(i, K){
    scanf("%d%d", &A,&B); A--;
    day[A] = B;
  }
  printf("%d\n", dfs(0, 0, 0));
  return 0;
}

C++: #include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MOD = 10000;

// dp[day][last][second]
int dp[100][3][2];
int plan[100];

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

    if(plan[0] == -1) {
        dp[0][0][0] = dp[0][1][0] = dp[0][2][0] = 1;
    }
    else {
        dp[0][plan[0]][0] = 1;
    }
    for(int day = 1; day < N; ++day) {
        if(plan[day] == -1) {
            for(int sauce = 0; sauce < 3; ++sauce) {
                for(int prev = 0; prev < 3; ++prev) {
                    if(prev != sauce) {
                        dp[day][sauce][0] += dp[day-1][prev][0] + dp[day-1][prev][1];
                    }
                    else {
                        dp[day][sauce][1] += dp[day-1][prev][0];
                    }
                }
            }
        }
        else {
            int sauce = plan[day];
            for(int prev = 0; prev < 3; ++prev) {
                if(prev != sauce) dp[day][sauce][0] += dp[day-1][prev][0] + dp[day-1][prev][1];
                else dp[day][sauce][1] += dp[day-1][prev][0];
            }
        }
        for(int sauce = 0; sauce < 3; ++sauce) {
            dp[day][sauce][0] %= MOD;
            dp[day][sauce][1] %= MOD;
        }
    }
    int sum = 0;
    for(int sauce = 0; sauce < 3; ++sauce) {
        sum += dp[N-1][sauce][0] + dp[N-1][sauce][1];
    }
    cout << sum%MOD << endl;
    return 0;
}

C++: #include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <utility>
#include <functional>

using namespace std;

#define MOD 10000

int main() {
	int n, k, a, b, plan[101] = { 0 }, dp[101][4][2] = { 0 };

	cin >> n >> k;
	for (int i = 0; i < k; ++i) {
		cin >> a >> b;
		plan[a] = b;
	}

	dp[1][1][0] = dp[1][2][0] = dp[1][3][0] = 1;
	for (int i = 1; i <= n; ++i) {
		if (plan[i] > 0) {
			for (int j = 1; j <= 3; ++j) {
				if (plan[i] != j)
					dp[i][j][0] = dp[i][j][1] = 0;
			}
		}
		if (i == n) break;
		for (int j = 1; j <= 3; ++j) {
			for (int k = 1; k <= 3; ++k) {
				if (j == k) {
					if (dp[i][j][0] > 0) {
						dp[i + 1][j][1] += dp[i][j][0] % MOD;
					}
				}
				else {
					dp[i + 1][k][0] += (dp[i][j][0] + dp[i][j][1]) % MOD;
				}
			}
		}
	}

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

	cout << sum % MOD << endl;

	return 0;
}

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

int n, k, p[101];
int dp[102][4][10]; //(1)日目,その日のパスタは(2),(3)日連続

int rec(int x, int y, int z){
	if(dp[x][y][z]>=0) return dp[x][y][z];
	
	int ret=0;
	
	if(z>=2) ret=0;
	else if(x==n+1) ret=1;	
	else{
		if(p[x]==0){ //その日のパスタは未定
			for(int i=1; i<=3; ++i){
				if(i==y) ret+=rec(x+1, i, z+1);
				else ret+=rec(x+1, i, 0);
					
			}
		}	
		else{
			if(y==p[x]) ret+=rec(x+1, p[x], z+1);
			else ret+=rec(x+1, p[x], 0);
		}
	}
	
	return dp[x][y][z]=ret%10000;
}

int main(){
	scanf(" %d %d", &n, &k);
	
	memset(p, 0, sizeof(p)); //初期化
	
	for(int i=0; i<k; ++i){
		int a, b;
		scanf(" %d %d", &a, &b);	
		p[a]=b; //a日目のpastaはb
	}
	
	memset(dp, -1, sizeof(dp));
	printf("%d\n", rec(1, 0, 0));
}