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;
#define f1 for(int x1=0;x1<3;x1++)
#define f2 for(int x2=0;x2<3;x2++)
#define f3 for(int x3=0;x3<3;x3++)

int n, k, a, b, p[100];
int c1[3][3][3], c2[3][3][3];

int total()
{
	int sum = 0;
	f1{ f2{ f3{
		sum += c2[x1][x2][x3];
	} } }
	return sum;
}

int main()
{

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

	for (int i = 0; i < n - 2; i++){
		if (!i){
			f1{ f2{ f3{
				c1[x1][x2][x3] = 1;
			} } }
		}
		else{
			int sum = 0;
			f1{ f2{
				f3{ sum += c2[x3][x1][x2]; }
				f3{ c1[x1][x2][x3] = sum; }
				sum = 0;
			} }
		}

		f1{ c1[x1][x1][x1] = 0; }

			if (p[i]){
				f1{ f2{ f3{
					if (p[i] != x1){ c1[x1][x2][x3] = 0; }
				} } }
			}
		if (p[i + 1]){
			f1{ f2{ f3{
				if (p[i + 1] != x2){ c1[x1][x2][x3] = 0; }
			} } }
		}
		if (p[i + 2]){
			f1{ f2{ f3{
				if (p[i + 2] != x3){ c1[x1][x2][x3] = 0; }
			} } }
		}

		f1{ f2{ f3{
			c2[x1][x2][x3] = c1[x1][x2][x3];
			c2[x1][x2][x3] %= 10000;
		} } }
	}

	cout << total() % 10000 << endl;
	return 0;
}

C++: #include<cstdio>
#include<queue>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<map>
#include<cmath>

using namespace std;

int n, k, sc[100] = {},dp[100][100][3];

int ans(int N, int K, int flag){
	if (flag == 2)return 0;
	int ret = 0;
	if (K != sc[N] && sc[N] >= 0)return 0;
	if (N == n - 1)return 1;
	for (int i = 0; i < 3; i++){
		if (i == K)ret += ans(N + 1, i, flag + 1);
		else ret += ans(N + 1, i, 0);
	}
	return dp[N][K][flag] = ret % 10000;
}

int main(){
	int answer = 0;
	for (int i = 0; i < 100; i++){
		sc[i] = -1;
	}
	scanf("%d %d", &n, &k);
	for (int i = 0; i < k; i++){
		int a,b;
		scanf("%d %d", &a, &b);
		sc[a-1] = b-1;
	}
	for (int i = 0; i < 3; i++){
		answer += ans(0, i, 0);
		answer %= 10000;
	}
	printf("%d\n", answer);
	return 0;
}

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

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(n) rep(i,n)
#define all(n) n.begin(),n.end()


const int MAXN = 100, MAXS = 6;
const int T = 1, C = 2, B = 3, TT = 4, CC = 5, BB = 6;
const int DS = 3;
const int res[6][4] = {{0,0}, {C,B,CC,BB},{B,T,BB,TT},{T,C,TT,CC}};


int main()
{
    int n, k; cin >> n >> k;
    long long dp[MAXS + 1][MAXN + 1] = {};
    int s[MAXN + 1] = {};
    int a, b;
    REP(k) {cin >> a; a--; cin >> s[a];}

    if(s[0] > 0) dp[s[0]][0] = 1;
    else dp[T][0] = dp[C][0] = dp[B][0] = 1;

    for(int i = 1; i< n; i++)
        if(s[i] > 0)
        {
            rep(j, 4)dp[s[i]][i] += dp[res[s[i]][j]][i - 1];
            dp[s[i] + DS][i] = dp[s[i]][i - 1];
        }
        else
        {
            for(int t = 1; t <= 3;t++)
                rep(j, 4)dp[t][i] += dp[res[t][j]][i - 1];
            for(int t = 4; t <= 6; t++)
                dp[t][i] = dp[t - DS][i - 1];
        }
    long long ans  = 0;
    REP(6) ans += dp[i + 1][n - 1];
    cout << ans% 10000 << endl;
    return 0;
}

C++: #include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	const int MOD = 10000;
	int pasta[3][3] = {0}; // 0d = 昨日パスタ, 1d = 今日パスタ
	int n, k;	// 桜乃かわいいよ桜乃
	vector<int> sc;	// スケジュール
	
	scanf("%d%d", &n, &k);
	sc.resize(n);
	for(int i = 0; i < k; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		sc[a - 1] = b;
	}
	
	for(int i = 0; i < 3; ++i) {
		for(int j = 0; j < 3; ++j) {
			
			if(sc[0] == 0 || sc[0] == i + 1)
				if(sc[1] == 0 || sc[1] == j + 1)
					pasta[i][j] = 1;
		}
	}
	
	for(int day = 2; day < n; ++day) {
		
		int next[3][3] = {0};
		
		for(int i = 0; i < 3; ++i) {
			for(int j = 0; j < 3; ++j) {
				
				if(sc[day] == 0 || sc[day] == j + 1) {
					for(int p = 0; p < 3; ++p)
						if(!(p == i && i == j))
							next[i][j] += pasta[p][i];
				}
			}
		}
		
		for(int i = 0; i < 3; ++i)
			for(int j = 0; j < 3; ++j)
				pasta[i][j] = next[i][j] % MOD;
	}
	
	int sum = 0;
	for(int i = 0; i < 3; ++i)
		for(int j = 0; j < 3; ++j)
			sum += pasta[i][j];
			
	printf("%d\n", sum % MOD);
	
	return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
int s1,day[105],a,b,n,k,ans;

int po(int x){
    ans=0;


    if(x==k+1){

            for(int i=1;i<=k;i++)cout << day[i] << endl;
            cout << endl;
            return 1;
    }

    s1=0;

    if(day[x]==0){
        for(int i=1;i<=3;i++){
            if(x>2){
            if(day[x-2]!=i&&day[x-1]!=i){
                    day[x]=i;
                    s1+=po(x+1);
                    day[x]=0;
                        }
                }else {
                    day[x]=i;
                    s1+=po(x+1);
                    day[x]=i;
                    }
        }
    }else {
        s1=po(x+1);

    }

    return s1;

}

int main(){

    cin >> k >> n;

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

    cout << po(1) << endl;



return 0;
}