#include<stdio.h>

#define MOD 10000

int N ,K ;
int plan[ 100 + 1 ][ 4 + 1 ][ 4 + 1 ] ;
int _now[ 100 + 1 ] ;

int Cnt( int day ,int prev ,int now )
{
	if( day == N )
	{
		return 1 ;
	}

	int &next = _now[ day ] ;
	if( next > 0 )
	{
		if( prev == now && now == next )
		{
			return 0 ;
		}
		
		return Cnt( day + 1 ,now ,next ) ;
	}

	int &value = plan[ day ][ prev ][ now ] ;
	if( value > 0 )
	{
		return value ;
	}

	int nex ,cnt = 0 ;
	for( nex = 1 ; nex <= 3 ; ++nex )
	{
		if( prev != now || now != nex )
		{
			cnt = (cnt + Cnt( day + 1 ,now ,nex )) % MOD ;
		}
	}

	return (value = cnt) ;
}


int main( void )
{
	scanf( "%d %d" ,&N ,&K ) ;

	++N ;

	int i ,day ,menu ;
	for( i = 0 ; i < K ; ++i )
	{
		scanf( "%d %d" ,&day ,&menu ) ;

		_now[ day ] = menu ;
	}

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

	return 0 ;
}
