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<vector>
#include<string>
#include<map>
#define int long long
using namespace std;

signed main() {
	int a, b;
	cin >> a >> b;
	map<int, int>c;
	for (int d = 0; d < b; d++) {
		int e;
		cin >> e; e--;
		cin >> c[e];
	}
	int dp[100][3][2]{};
	if (c[0])dp[0][c[0]-1][0] = 1;
	else dp[0][0][0] = dp[0][1][0] = dp[0][2][0] = 1;
	for (int f = 1; f < a; f++) {
		dp[f][0][0] = dp[f - 1][1][0] + dp[f - 1][1][1] + dp[f - 1][2][0] + dp[f - 1][2][1];
		dp[f][1][0] = dp[f - 1][0][0] + dp[f - 1][0][1] + dp[f - 1][2][0] + dp[f - 1][2][1];
		dp[f][2][0] = dp[f - 1][0][0] + dp[f - 1][0][1] + dp[f - 1][1][0] + dp[f - 1][1][1];
		dp[f][0][1] = dp[f - 1][0][0];
		dp[f][1][1] = dp[f - 1][1][0];
		dp[f][2][1] = dp[f - 1][2][0];
		switch (c[f]) {
		case 1:dp[f][1][0] = dp[f][1][1] = dp[f][2][0] = dp[f][2][1] = 0; break;
		case 2:dp[f][0][0] = dp[f][0][1] = dp[f][2][0] = dp[f][2][1] = 0; break;
		case 3:dp[f][0][0] = dp[f][0][1] = dp[f][1][0] = dp[f][1][1] = 0; break;
		}
		for (int x = 0; x < 3; x++) {
			for (int y = 0; y < 2; y++) {
				dp[f][x][y] %= 10000;
			}
		}
	}
	int s = 0;
	for (int x = 0; x < 3; x++) {
		for (int y = 0; y < 2; y++) {
			s += dp[a-1][x][y];
		}
	}
	cout << s%10000 << endl;
}

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

enum Sauce{Tomato=1, Cream=2, Basil=3, NOT_DETERMINED=0};
enum Seq{SAME, DIFF};

int N, K;
static Sauce* sauceary;
const int divisor = 10000;

int schedule(int i, Sauce yesterday, Seq seq);

int main(){
	cin >> N >> K;

	sauceary = new Sauce[N+1];
	for (int i = 0; i <= N; i++) sauceary[i] = NOT_DETERMINED;

	for (int i = 0; i < K; i++){
		int A, B;
		cin >> A >> B;
		sauceary[A] = (Sauce)B;
	}

	int ans;
	if (sauceary[1] == NOT_DETERMINED){
		ans = schedule(2, Tomato, DIFF) + schedule(2, Cream, DIFF) + schedule(2, Basil, DIFF);
	} else {
		ans = schedule(2, sauceary[1], DIFF);
	}

	cout << ans % divisor << endl;

	delete[] sauceary;

	return 0;
}

int schedule(int i, Sauce yesterday, Seq seq){
	if (i == N+1) return 1;
	if (seq == SAME && yesterday == sauceary[i]) return 0;

	if (sauceary[i] == NOT_DETERMINED){
		switch (yesterday){
		case Tomato: 
			if (seq == SAME) return (schedule(i+1, Cream, DIFF) + schedule(i+1, Basil, DIFF)) % divisor;
			else if (seq == DIFF) return (schedule(i+1, Tomato, SAME) + schedule(i+1, Cream, DIFF) + schedule(i+1, Basil, DIFF)) % divisor;
		case Cream:
			if (seq == SAME) return (schedule(i+1, Tomato, DIFF) + schedule(i+1, Basil, DIFF)) % divisor;
			else if (seq == DIFF) return (schedule(i+1, Tomato, DIFF) + schedule(i+1, Cream, SAME) + schedule(i+1, Basil, DIFF)) % divisor;
		case Basil:
			if (seq == SAME) return (schedule(i+1, Tomato, DIFF) + schedule(i+1, Cream, DIFF)) % divisor;
			else if (seq == DIFF) return (schedule(i+1, Tomato, DIFF) + schedule(i+1, Cream, DIFF) + schedule(i+1, Basil, SAME)) % divisor;
		}
	}
	else {
		if (yesterday == sauceary[i]) return schedule(i+1, sauceary[i], SAME) % divisor;
		else return schedule(i+1, sauceary[i], DIFF) % divisor;
	}
}

C++: #include<iostream>
using namespace std;
int main(){
	int N,K,a,b;
	cin>>N>>K;
	int dp[110][4]={};
	for(int i=0;i<K;i++){
		cin>>a>>b;
		dp[a][b]=1;
	}
	if(dp[1][1]==0 && dp[1][2]==0 && dp[1][3]==0){
		for(int i=1;i<=3;i++){
			dp[1][i]=1;
		}
	}

	for(int i=1;i<=N;i++){
		if(dp[i+1][1]==0 && dp[i+1][2]==0 && dp[i+1][3]==0){
			for(int j=1;j<=3;j++){
				if(dp[i+2][j]>0 && dp[i+3][j]>0){
					dp[i+1][j]=0;


				}

				else	if(dp[i][j]>0 && dp[i+2][j]>0){
					if(j==1){
						dp[i+1][j]=(dp[i][2]+dp[i][3])%10000;
					}
					else if(j==2){
						dp[i+1][j]=(dp[i][1]+dp[i][3])%10000;
					}
					else{
						dp[i+1][j]=(dp[i][1]+dp[i][2])%10000;
					}


				}
				else if(dp[i+2][j]>0 && dp[i+3][j]>0){
					dp[i+1][j]=0;


				}
				else if(dp[i-1][j]>0  && dp[i][j]>0){
					if(j==1){

						dp[i+1][j]=((+dp[i][2]+dp[i][3])%10000+(+dp[i-1][2]+dp[i-1][3])%10000)%10000;
					}
					else if(j==2){
						dp[i+1][j]=((+dp[i][1]+dp[i][3])%10000+(+dp[i-1][1]+dp[i-1][3])%10000)%10000;
					}
					else{
						dp[i+1][j]=((+dp[i][2]+dp[i][1])%10000+(+dp[i-1][2]+dp[i-1][1])%10000)%10000;
					}


				}

				else{
					dp[i+1][j]=((dp[i][1]+dp[i][2])%10000+dp[i][3])%10000;
				}
			}
		}
		else{
			for(int j=1;j<=3;j++){
				if(dp[i+1][j]==1){
					dp[i+1][j]=((dp[i][1]+dp[i][2])%10000+dp[i][3])%10000;
				}
			}
		}
	}
		
	cout<<(dp[N][1]+dp[N][2]+dp[N][3])%10000<<endl;
	return 0;
	

	}