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

int main(){
	int h,i,j,n,k,b,*p,y[81][5],u=0;
	queue<int> q,w,e,r,t;
	
	cin >> n >> k;
	p = new int[n+4];
	
	for(i=0; i<n+4; i++){
		p[i] = 0;
	}
	
	for(i=0; i<k; i++){
		cin >> b;
		cin >> p[b+1];
	}
	
	q.push(1);
	w.push(0);
	e.push(0);
	r.push((p[3])?p[3]:0);
	t.push((p[4])?p[4]:0);
	
	for(i=2; i<n+2; i++){
		b=0;
		for(; !q.empty(); ){
			for(h=1; h<4; h++){
				if(p[i]){
					y[b][0] = q.front();
					y[b][1] = e.front();
					y[b][2] = p[i];
					y[b][3] = t.front();
					y[b++][4] = (p[i+3])?p[i+3]:0;
					break;
				}else if(!((w.front() == h && e.front() == h) || (e.front() == h && h == r.front()) || (h == r.front() && h == t.front()))){
					y[b][0] = q.front();
					y[b][1] = e.front();
					y[b][2] = h;
					y[b][3] = t.front();
					y[b++][4] = (p[i+3])?p[i+3]:0;
				}
			}
			q.pop();
			w.pop();
			e.pop();
			r.pop();
			t.pop();
		}
		for(j=0; j<b; j++){
			if(y[j][0] != -1){
				for(h=0; h<b; h++){
					if((j != h)&&(y[j][1] == y[h][1])&&(y[j][2] == y[h][2])&&(y[j][3] == y[h][3])&&(y[j][4] == y[h][4])){
						y[j][0] += y[h][0];
						y[j][0] %= 10000;
						y[h][0] = -1;
					}
				}
				q.push(y[j][0]);
				w.push(y[j][1]);
				e.push(y[j][2]);
				r.push(y[j][3]);
				t.push(y[j][4]);
			}
		}
	}
	
	for(; !q.empty(); ){
		u += q.front();
		q.pop();
	}
	
	cout << u%10000 << endl;
	return 0;
}

C++: #include<iostream>
#include<cstring>
#include<map>
using namespace std;
typedef long long int ll;
ll dfs(int day,int r1,int r2);
ll dp[101][4][4];
int n,k;
map<int,int> plan;
int main(){
	cin >> n >> k;
	for(int i=0;i<k;i++){
		int a,b; cin >> a >> b;
		a--; plan[a] = b;
	}
	memset(dp,-1,sizeof(dp));
	cout << dfs(0,0,0) << endl;
}

ll dfs(int day,int r1,int r2){
	if(day==n) return 1;
	if(dp[day][r1][r2] != -1) return dp[day][r1][r2];
	if(plan[day] != 0){
		if(r1 == r2 && r1 == plan[day]) return 0;
		else return dfs(day+1,plan[day],r1)%10000;
	}
	ll ret = 0;
	for(int i=1;i<=3;i++){
		if(r1 == r2 && r1 == i) continue;
		ret += dfs(day+1,i,r1)%10000;
	}
	return dp[day][r1][r2] = ret%10000;
}

C++: #include<stdio.h>
#include<algorithm>
using namespace std;
int mod=10000;
int dp[110][3][3];
int p[110];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<110;i++)p[i]=-1;
	for(int i=0;i<b;i++){
		int s,t;scanf("%d%d",&s,&t);
		s--;t--;
		p[s]=t;
	}
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			if(p[0]!=-1&&p[0]!=i)continue;
			if(p[1]!=-1&&p[1]!=j)continue;
			dp[2][i][j]=1;
		}
	}
	for(int i=2;i<a;i++){
		for(int j=0;j<3;j++)for(int k=0;k<3;k++)for(int l=0;l<3;l++){
			if(j==k&&k==l)continue;
			if(p[i]!=-1&&l!=p[i])continue;
			dp[i+1][k][l]=(dp[i+1][k][l]+dp[i][j][k])%mod;
		}
	}
	int ret=0;
	for(int i=0;i<3;i++)for(int j=0;j<3;j++){
		ret=(ret+dp[a][i][j])%mod;
	}
	printf("%d\n",ret);
}

C++: #include <bits/stdc++.h>

using namespace std;

#define MOD 10000

int a[101];

int dp[101][4][4];

int n, k;

int rec(int day, int pp, int p)
{
	if (day > n) return 1;

	if (dp[day][pp][p] >= 0) return dp[day][pp][p];

	int res = 0;

	if (a[day]) {
		if (a[day] != pp || a[day] != p) {
			res = rec(day + 1, p, a[day]);
			res %= MOD;
		}
	} else {
		for (int i = 1; i <= 3; ++i) {
			if (pp == p && p == i) continue;
			res += rec(day + 1, p, i);
			res %= MOD;
		}
	}

	return dp[day][pp][p] = res;
}

int main()
{
	cin >> n >> k;

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

	memset(dp, -1, sizeof(dp));

	printf("%d\n", rec(1, 0, 0));
}

C++: #include <bits/stdc++.h>
#define rep(i,l,n) for(int i=l;i<n;i++)
#define all(a) a.begin(),a.end()
#define o(a) cout<<a<<endl
using namespace std;
typedef long long lint;
typedef vector<int> vi;
typedef vector<lint> vli;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

int main(){
    int n,k;
    cin>>n>>k;
    int num[110];
    memset(num,-1,sizeof(num));
    rep(i,0,k){
    	int a,b;
    	cin>>a>>b;
    	a--; b--;
    	num[a]=b;
    }
    //dp[i][j][k]??????i+1??\??????j+1?????????????????????k+1??\??£?¶???§?£???????????????¨????????¶????????°???10000??§?????£??????????????\???
    int dp[110][3][2]={};
    if(num[0]==-1) rep(i,0,3) dp[0][i][0]=1;
    else dp[0][num[0]][0]=1;
    rep(i,1,n){
    	//?£????????????????????±??????£??????????????´???
    	if(num[i]==-1){
    		rep(j,0,3){
    			dp[i][j][1]=(dp[i][j][1]+dp[i-1][j][0])%10000;
    			rep(k,0,3){
    				if(j==k) continue;
    				dp[i][j][0]=(dp[i][j][0]+dp[i-1][k][0]+dp[i-1][k][1])%10000;
    			}
    		}
    	}
    	//?£????????????????????±??????£???????????´???
    	else{
    		int id=num[i];
    		dp[i][id][1]=(dp[i][id][1]+dp[i-1][id][0])%10000;
    		rep(k,0,3){
    			if(id==k) continue;
    			dp[i][id][0]=(dp[i][id][0]+dp[i-1][k][0]+dp[i-1][k][1])%10000;
    		}
    	}
    }
    int sum=0;
    rep(i,0,3) rep(j,0,2) sum+=dp[n-1][i][j];
    o(sum%10000);
}