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<bits/stdc++.h>
#define rep(a,b) for(int a=0;a<b;a++)
#define int long long int

using namespace std;

const int INF = 1000000009;

int day,al;
int almost[200];
int ans=1;
int used[200];

int pasu(int p){
    if(p==3)return 1;
    else if(p==2)return 3;
    else if(p==1)return 2;
}

int pasu2(int p){
    if(p==3)return 2;
    else if(p==2)return 1;
    else if(p==1)return 3;
}

int kaburi1(int date){
    if(almost[date+1]!=0){
        return almost[date+1];
    }else return 0;
}

int kaburi2(int date){
    if(almost[date+2]!=0){
        return almost[date+2];
    }else return 0;
}

int pasuta(int d2, int d1, int dd1, int dd2,int date){
    if(date>day)return 1;
    //else if(used[date])return;
    else if(almost[date]!=0){
        //used[date]=1;
        return pasuta(d1,almost[date],kaburi1(date+1),kaburi2(date+1),date+1)%10000;
    }/*else if(d2==d1&&d1==dd1&&d1!=0){

        //used[date]=1;
//        cout << "a" << date;
       // if(d2==dd1){
            //ans=ans*2;
            return pasuta(dd1,dd2,kaburi1(date+3),kaburi2(date+3),date+3)+pasuta(dd1,dd2,kaburi1(date+3),kaburi2(date+3),date+3);
    //}else{
         //   return pasuta(dd1,dd2,kaburi1(date+3),kaburi2(date+3),date+3);
      //  }
    }*/else if((d2==d1||d1==dd1)&&d1!=0){
        //used[date]=1;

  //      cout << "b" << date;
        //ans=ans*2;
        return (pasuta(d1,pasu(d1),kaburi1(date+1),kaburi2(date+1),date+1)+pasuta(d1,pasu2(d1),kaburi1(date+1),kaburi2(date+1),date+1))%10000;
    }else{
      //  used[date]=1;
    //    cout << "c" << date;
        //ans=ans*3;
        return (pasuta(d1,1,kaburi1(date+1),kaburi2(date+1),date+1)+
        pasuta(d1,2,kaburi1(date+1),kaburi2(date+1),date+1)+
        pasuta(d1,3,kaburi1(date+1),kaburi2(date+1),date+1))%10000;
    }
}

signed main(){
    fill(almost,almost+200,0);
    fill(used,used+200,0);
    cin >> day >> al;
    rep(a,al){
        int da,pa;
        cin >> da >> pa;
        almost[da]=pa;
    }
    ans = pasuta(0,0,almost[2],almost[3],1);
    cout << ans << endl;
return 0;
}

C++: //うわあああああああ
#include <iostream>
#include <iomanip>
using namespace std;

int N, K;
int DP[3][101];

void debug(void) {
  for (int d=0; d<=N; d++) {
    for (int k=0; k<3; k++) {
      cout << setw(8) << DP[k][d];
    }
    cout << endl;
  }
} 

int main(void) {
  for (int k=0; k<3; k++) {
    DP[k][0] = -1;
    DP[k][1] = 1;
  }

  cin >> N >> K;
  for (int i=0; i<K; i++) {
    int A, B;
    cin >> A >> B;
    DP[B%3][A] = -1;
    DP[(B+1)%3][A] = -1;
  }

  for (int d=1; d<N; d++) {
    for (int k=0; k<3; k++) {
      if (DP[k][d] != -1) {
	for (int nk=0; nk<3; nk++) {
	  if (DP[nk][d+1] != -1) {
	    DP[nk][d+1] += DP[k][d];
	    if (k==nk && DP[k][d-1]!=-1) {
	      int sub = DP[k][d];
	      for (int pk=0; pk<3; pk++) {
		if (k!=pk && DP[pk][d-1]!=-1) {
		  sub -= DP[pk][d-1];
		}
	      }
	      DP[nk][d+1] -= sub;
	    }
	  }
	}
      }
      DP[k][d+1] %= 10000;
    }
  }

  int sum = 0;
  for (int k=0; k<3; k++) {
    if (DP[k][N] != -1) {
      sum += DP[k][N];
    }
  }

  cout << sum%10000 << endl;

  return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;

const int MOD = 1e4;

int n, k;
int sc[100];
int dp[101][4][4];

int main()
{
	scanf("%d %d", &n, &k);
	
	for (int i = 0; i < n; i++) sc[i] = 3;
	for (int i = 0; i < k; i++){
		int a, b;
		scanf("%d %d", &a, &b);
		sc[--a] = --b;
	}
	
	dp[0][3][3] = 1;
	for (int i = 0; i < n; i++){
		for (int a = 0; a < 4; a++){
			for (int b = 0; b < 4; b++){
				for (int c = 0; c < 3; c++){
					if (sc[i] < 3 && sc[i] != c) continue;
					if (a == b && b == c) continue;
					dp[i + 1][b][c] = (dp[i + 1][b][c] + dp[i][a][b]) % MOD;
				}
			}
		}
	}
	
	int res = 0;
	for (int i = 0; i < 4; i++){
		for (int j = 0; j < 4; j++){
			res = (res + dp[n][i][j]) % MOD;
		}
	}
	printf("%d\n", res);
}

C++: #include<bits/stdc++.h>
#define modulo 10000;
using namespace std;

int dp[114][5][14];//day yesterday today
int pa[114];//pasta

int main(){
	int n,ka;
	cin>>n>>ka;
	for(int i=0;i<ka;i++){
		int a,b;
		cin>>a>>b;
		pa[a]=b;
		}
		
	if(pa[1]){
		for(int i=0;i<1;i++)dp[1][i][pa[1]-1]++;
		}
	else{
		for(int i=0;i<1;i++)
		for(int j=0;j<3;j++)dp[1][i][j]++;
		}	
		
	for(int x=2;x<=n;x++){
		if(pa[x]==1){
			for(int i=0;i<3;i++){
				for(int j=0;j<3;j++){
					if(i==j&&j==0)continue;
					dp[x][i][0]+=dp[x-1][j][i];//
					dp[x][i][0]%=modulo;
					}
				}
			}
		else if(pa[x]==2){
			for(int i=0;i<3;i++){
				for(int j=0;j<3;j++){
					if(i==j&&j==1)continue;
					dp[x][i][1]+=dp[x-1][j][i];//
					dp[x][i][1]%=modulo;
					}
				}
			}
		else if(pa[x]==3){
			for(int i=0;i<3;i++){
				for(int j=0;j<3;j++){
					if(i==j&&j==2)continue;
					dp[x][i][2]+=dp[x-1][j][i];//
					dp[x][i][2]%=modulo;
					}
				}
			}
		else{
			for(int i=0;i<3;i++){
				for(int j=0;j<3;j++){
					for(int k=0;k<3;k++){
						if(x!=2){
						if(i==j&&j==k)continue;}
						dp[x][i][j]+=dp[x-1][k][i];//
						dp[x][i][j]%=modulo;
						}
					}
				}
			}
			}	
	int ans=0;
		for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)ans+=dp[n][i][j];
		ans%=modulo;
		cout<<ans<<endl;
		return 0;
	}