import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int niti[] = new int [n]; // ?±??????£???????????\??????
		int pasuta[] = new int [k]; //????±??????£???????????????????????????
		int tomato1 = 0,tomato2 = 0,tomato99 = 0,tomato88 = 0;
		int kuri1 = 0,kuri2 = 0,kuri99 = 0,kuri88 = 0;
		int baji1 = 0,baji2 = 0,baji99 = 0,baji88 = 0;
		for(int i = 0 ; i < k;i++){
			niti[i] = sc.nextInt();
			pasuta[i] = sc.nextInt();
		}
		int box,work;
		for(int i = 0; i < k; i++) { //??????????????????
			box = i;
			for(int m = i + 1; m < k; m++) {
				if(niti[m] < niti[box]){
					box = m;
				}
			}
			work = niti[i]; 
			niti[i] = niti[box]; 
			niti[box] = work;
			work = pasuta[i]; 
			pasuta[i] = pasuta[box]; 
			pasuta[box] = work;
		}
		for(int i = 0;i<k;i++){
			//System.out.println("?±??????£?????\?????????"+niti[i]+"?????????????????????"+pasuta[i]);
		}
		int count = 0;
		for(int i = 0;i<n;i++){
			if(i==(niti[count]-1)){
				if(i==0){
					if(pasuta[count]==1){
						tomato1++;
					}
					else if(pasuta[count]==2){
						kuri1++;
					}
					else{
						baji1++;
					}
				}
				else if(pasuta[count]==1){//??????????????¨??????
					tomato2 = tomato1;
					tomato1 = kuri1 + kuri2 + baji1 + baji2;
					kuri1 = 0;
					kuri2 = 0;
					baji1 = 0;
					baji2 = 0;
					tomato1 = tomato1 % 10000;
					tomato2 = tomato2 % 10000;
					kuri1 = kuri1 % 10000;
					kuri2 = kuri2 % 10000;
					baji1 = baji1 % 10000;
					baji2 = baji2 % 10000;
				}
				else if(pasuta[count]==2){//?????????????????¨??????
					kuri2 = kuri1;
					kuri1 = tomato1 + tomato2 + baji1 + baji2;
					tomato1 = 0;
					tomato2 = 0;
					baji1 = 0;
					baji2 = 0;
					tomato1 = tomato1 % 10000;
					tomato2 = tomato2 % 10000;
					kuri1 = kuri1 % 10000;
					kuri2 = kuri2 % 10000;
					baji1 = baji1 % 10000;
					baji2 = baji2 % 10000;
				}
				else{//??????????????¨??????
					baji2 = baji1;
					baji1 = tomato1 + tomato2 + kuri1 + kuri2;
					tomato1 = 0;
					tomato2 = 0;
					kuri1 = 0;
					kuri2 = 0;
					tomato1 = tomato1 % 10000;
					tomato2 = tomato2 % 10000;
					kuri1 = kuri1 % 10000;
					kuri2 = kuri2 % 10000;
					baji1 = baji1 % 10000;
					baji2 = baji2 % 10000;
					/*System.out.println("?????¨"+(i+1)+"??\???");
					System.out.println("??????????????\??£?¶?"+tomato2);
					System.out.println("??????????????\??£?¶?"+tomato1);
					System.out.println("??????????????\??£?¶?"+kuri2);
					System.out.println("??????????????\??£?¶?"+kuri1);
					System.out.println("??????????????\??£?¶?"+baji2);
					System.out.println("??????????????\??£?¶?"+baji1);
					*/
				}
				count++;
			}
			else if(i==0){
				tomato1++;
				kuri1++;
				baji1++;
			}
			else{
				tomato99 = tomato1;
				tomato88 = tomato2;
				kuri99 = kuri1;
				kuri88 = kuri2;
				baji99 = baji1;
				baji88 = baji2;
				tomato1 = kuri99+kuri88+baji99+baji88;
				kuri1 = baji99+baji88+tomato99+tomato88;
				baji1 = tomato99+tomato88+kuri99+kuri88;
				tomato2 = tomato99;
				kuri2 = kuri99;
				baji2 = baji99;
				tomato1 = tomato1 % 10000;
				tomato2 = tomato2 % 10000;
				kuri1 = kuri1 % 10000;
				kuri2 = kuri2 % 10000;
				baji1 = baji1 % 10000;
				baji2 = baji2 % 10000;
				/*System.out.println("?????¨"+(i+1)+"??\???");
				System.out.println("??????????????\??£?¶?"+tomato2);
				System.out.println("??????????????\??£?¶?"+tomato1);
				System.out.println("??????????????\??£?¶?"+kuri2);
				System.out.println("??????????????\??£?¶?"+kuri1);
				System.out.println("??????????????\??£?¶?"+baji2);
				System.out.println("??????????????\??£?¶?"+baji1);
				*/
			}
		}
		int x = tomato1+tomato2+kuri1+kuri2+baji1+baji2;
		x = x % 10000;
		System.out.println(x);
	}
}
				

Measured memory_bytes: 19676