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++: //
//  main.cpp

#include <iostream>
using namespace std;
const int tomato = 1;
const int cream = 2;
const int basil = 3;
int dp[101][4][4][4];//i??\??????????????????a???i-1??\??????????????????b???i-2??\??????????????????c??¨???????????????????????????????????°???
int day[101]={};
int n,k;

int pasta(int i,int a,int b,int c){//i??\??????i??\???????????????a???i-1??\???????????????b???i-2??\???????????????c???
	if(a == b&&b == c)return 0;
	if(dp[i][a][b][c]){//?????§????¨??????????(!=0)????????????????????????
		return dp[i][a][b][c];
	}
	if(day[i] && day[i] != a)return 0;//?????????????±???????????????????????????????????????¨?????????????????????????????????
	if(day[i-1] && day[i-1] != b)return 0;
	if(day[i-2] && day[i-2] != c)return 0;
	if(i == 3){
		dp[i][a][b][c] = 1;
		return dp[i][a][b][c];
	}
	
	int ret=0;
	for(int j=1;j<4;j++){
		ret += pasta(i-1,b,c,j);
	}
	dp[i][a][b][c] = ret % 10000;
	return dp[i][a][b][c];
}

int main(){	
	
	cin >> n >> k;
	for(int i=0;i<101;i++){
		day[i] = 0;
	}
	int input;
	for(int i=1;i<=k;i++){
		cin >> input;
		cin >> day[input];
	}
	
	for(int i=0;i<101;i++){
		for(int j=0;j<4;j++){
			for(int k=0;k<4;k++){
				for(int r=0;r<4;r++){
					dp[i][j][k][r] = 0;
				}
			}
		}
	}
	
	int answer=0;
	for(int i=1;i<4;i++){
		for(int j=1;j<4;j++){
			for(int k=1;k<4;k++){
				answer += pasta(n,i,j,k) % 10000;
			}
		}
	}
	cout << answer % 10000 << endl;
	
	return 0;
}

C++: #include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef vector<pii> vp;

int gcd(int a, int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int lcm(int a, int b){
    return a/gcd(a,b)*b;
}

int dp[105][3][3];

signed main(void) {
    int n,k;
    cin >> n >> k;
    vi v(n,-1);
    rep(i,k){
        int a,b;
        cin >> a >> b;
        v[a-1] = b-1;
    }
    rep(i,3)rep(j,3){
        if(v[0] != -1 && v[0] != i)continue;
        if(v[1] != -1 && v[1] != j)continue;
        dp[2][i][j] = 1;
    }
    loop(i,2,n)rep(j,3)rep(k,3)if(dp[i][j][k]){
        //cout << i << " " << j << " " << k << " " << dp[i][j][k] << " " << v[i] << endl;;
        rep(l,3){
            if(j == k && k == l)continue;
            if(v[i] != -1 && v[i] != l)continue;
            (dp[i+1][k][l] += dp[i][j][k]) %= 10000;
        }
    }
    int ans = 0;
    rep(i,3)rep(j,3)(ans += dp[n][i][j]) %= 10000;
    cout << ans << endl;
}

C++: #include "stdio.h"

int day;
int decide;
int pasta[101] = {};
int dp[101][4][4] = {};
int box;
int ans = 0;

int main() {
	scanf("%d %d", &day,&decide);
	for (int i = 0; i < decide; i++) {
		scanf("%d", &box);
		scanf("%d", &pasta[box]);
	}
	//for (int i = 1; i < day+1; i++)printf("%d\n", pasta[i]);
	if (pasta[1] == 0) {
		dp[1][0][1] = 1;
		dp[1][0][2] = 1;
		dp[1][0][3] = 1;
	}
	else {
		dp[1][0][pasta[1]] = 1;
	}
	if (pasta[2] == 0) {
		for (int i = 1; i < 4; i++) {
			for (int j = 1; j < 4; j++) {
				dp[2][i][j] += dp[1][0][i];
			}
		}
	}
	else {
		for (int i = 1; i < 4; i++) {
			dp[2][i][pasta[2]] += dp[1][0][i];
		}
	}
	for (int i = 3; i <= day; i++) {
		if (pasta[i] == 0) {
			for (int j = 1; j < 4; j++) {
				for (int k = 1; k < 4; k++) {
					for (int l = 1; l < 4; l++) {
						if (!((l == j)&&(l == k))) {
							dp[i][k][l] += dp[i - 1][j][k];
							dp[i][k][l] %= 10000;
			//				printf("%d??\??????%d %d %d????£?????????????%d??????\n", i,j, k, l, dp[i][k][l]);
						}
					}
				}
			}
		}
		else {
			for (int j = 1; j < 4; j++) {
				for (int k = 1; k < 4; k++) {
					if (!((pasta[i] == j)&&(pasta[i] == k))) {
						dp[i][k][pasta[i]] += dp[i - 1][j][k];
						dp[i][k][pasta[i]] %= 10000;
			//			printf("%d??\??????%d %d %d????£?????????????%d??????\n", i,j, k, pasta[i], dp[i][k][pasta[i]]);
					}
				}
			}
		}
	}
	if (pasta[day] == 0) {
		for (int i = 1; i < 4; i++) {
			for (int j = 1; j < 4; j++) {
				ans += dp[day][i][j];
				ans %= 10000;
			}
		}
	}
	else {
		for (int i = 1; i < 4; i++) {
			ans += dp[day][i][pasta[day]];
			ans %= 10000;
		}
	}
	printf("%d\n", ans);
	return 0;
}