시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 389 156 117 43.015%

문제

상근이는 매일 저녁으로 파스타를 만들어 먹는다. 상근이가 만들 수 있는 파스타는 총 세 종류로 토마토 소스, 크림 소스, 바질 소스이다.

상근이는 앞으로 N일 동안 먹을 파스타를 계획하려고 한다. 매일 매일 세 종류의 파스타 중 한 종류를 선택할 것이다. 하지만, 같은 파스타를 계속해서 먹으면 질려버릴 수 있기 때문에, 3일 이상 연속해서 같은 파스타를 먹지 않는다.

또, N일 중 K일에 먹을 파스타는 미리 정해두었다.

N과 K일에 먹을 파스타가 주어졌을 때, 가능한 계획의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 100, 1 ≤ K ≤ N)

둘째 줄부터 K개 줄에는, 미리 파스타를 정해놓은 날의 정보가 주어진다. 이 정보는 Ai Bi와 같은 형식이며, Ai일에 먹을 파스타는 Bi라는 뜻이다. 이때, Bi = 1이면 토마토 소스, 2이면 크림 소스, 3이면 바질 소스이다. Ai는 모두 다르다.

출력

상근이가 세울 수 있는 계획의 수를 10000으로 나눈 나머지를 출력한다.

예제 입력 1

5 3
3 1
1 1
4 2

예제 출력 1

6

힌트

예제의 경우에는 총 6가지가 가능하다.

1,2,1,2,1

1,2,1,2,2

1,2,1,2,3

1,3,1,2,1

1,3,1,2,2

1,3,1,2,3

W3sicHJvYmxlbV9pZCI6IjU1NDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMGNcdWMyYTRcdWQwYzAiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWI5ZTRcdWM3N2MgXHVjODAwXHViMTQxXHVjNzNjXHViODVjIFx1ZDMwY1x1YzJhNFx1ZDBjMFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWM1YjQgXHViYTM5XHViMjk0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVkMzBjXHVjMmE0XHVkMGMwXHViMjk0IFx1Y2QxZCBcdWMxMzggXHVjODg1XHViOTU4XHViODVjIFx1ZDFhMFx1YjljOFx1ZDFhMCBcdWMxOGNcdWMyYTQsIFx1ZDA2Y1x1YjliYyBcdWMxOGNcdWMyYTQsIFx1YmMxNFx1YzljOCBcdWMxOGNcdWMyYTRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM1NWVcdWM3M2NcdWI4NWMgTlx1Yzc3YyBcdWIzZDlcdWM1NDggXHViYTM5XHVjNzQ0IFx1ZDMwY1x1YzJhNFx1ZDBjMFx1Yjk3YyBcdWFjYzRcdWQ2OGRcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWI5ZTRcdWM3N2MgXHViOWU0XHVjNzdjIFx1YzEzOCBcdWM4ODVcdWI5NThcdWM3NTggXHVkMzBjXHVjMmE0XHVkMGMwIFx1YzkxMSBcdWQ1NWMgXHVjODg1XHViOTU4XHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVhYzE5XHVjNzQwIFx1ZDMwY1x1YzJhNFx1ZDBjMFx1Yjk3YyBcdWFjYzRcdWMxOGRcdWQ1NzRcdWMxMWMgXHViYTM5XHVjNzNjXHViYTc0IFx1YzljOFx1YjgyNFx1YmM4NFx1YjliNCBcdWMyMTggXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgM1x1Yzc3YyBcdWM3NzRcdWMwYzEgXHVjNWYwXHVjMThkXHVkNTc0XHVjMTFjIFx1YWMxOVx1Yzc0MCBcdWQzMGNcdWMyYTRcdWQwYzBcdWI5N2MgXHViYTM5XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViNjEwLCBOXHVjNzdjIFx1YzkxMSBLXHVjNzdjXHVjNWQwIFx1YmEzOVx1Yzc0NCBcdWQzMGNcdWMyYTRcdWQwYzBcdWIyOTQgXHViYmY4XHViOWFjIFx1YzgxNVx1ZDU3NFx1YjQ1MFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0Tlx1YWNmYyBLXHVjNzdjXHVjNWQwIFx1YmEzOVx1Yzc0NCBcdWQzMGNcdWMyYTRcdWQwYzBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhYzAwXHViMmE1XHVkNTVjIFx1YWNjNFx1ZDY4ZFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjZmMgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgzICZsZTsgTiAmbGU7IDEwMCwgMSAmbGU7IEsgJmxlOyBOKTxcL3A+XHJcblxyXG48cD5cclxuXHRcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIEtcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0LCBcdWJiZjhcdWI5YWMgXHVkMzBjXHVjMmE0XHVkMGMwXHViOTdjIFx1YzgxNVx1ZDU3NFx1YjE5M1x1Yzc0MCBcdWIwYTBcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YzgxNVx1YmNmNFx1YjI5NCBBPHN1Yj5pPFwvc3ViPiBCPHN1Yj5pPFwvc3ViPlx1YzY0MCBcdWFjMTlcdWM3NDAgXHVkNjE1XHVjMmRkXHVjNzc0XHViYTcwLCBBPHN1Yj5pPFwvc3ViPlx1Yzc3Y1x1YzVkMCBcdWJhMzlcdWM3NDQgXHVkMzBjXHVjMmE0XHVkMGMwXHViMjk0IEI8c3ViPmk8XC9zdWI+XHViNzdjXHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC4gXHVjNzc0XHViNTRjLCBCPHN1Yj5pPFwvc3ViPiA9IDFcdWM3NzRcdWJhNzQgXHVkMWEwXHViOWM4XHVkMWEwIFx1YzE4Y1x1YzJhNCwgMlx1Yzc3NFx1YmE3NCBcdWQwNmNcdWI5YmMgXHVjMThjXHVjMmE0LCAzXHVjNzc0XHViYTc0IFx1YmMxNFx1YzljOCBcdWMxOGNcdWMyYTRcdWM3NzRcdWIyZTQuIEFpXHViMjk0IFx1YmFhOFx1YjQ1MCBcdWIyZTRcdWI5NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YzEzOFx1YzZiOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNjNFx1ZDY4ZFx1Yzc1OCBcdWMyMThcdWI5N2MgMTAwMDBcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlxyXG5cdFx1YzYwOFx1YzgxY1x1Yzc1OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjZDFkIDZcdWFjMDBcdWM5YzBcdWFjMDAgXHVhYzAwXHViMmE1XHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQxLDIsMSwyLDE8XC9wPlxyXG48cD5cclxuXHQxLDIsMSwyLDI8XC9wPlxyXG48cD5cclxuXHQxLDIsMSwyLDM8XC9wPlxyXG48cD5cclxuXHQxLDMsMSwyLDE8XC9wPlxyXG48cD5cclxuXHQxLDMsMSwyLDI8XC9wPlxyXG48cD5cclxuXHQxLDMsMSwyLDM8XC9wPlxyXG5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1NTQ2IiwicHJvYmxlbV9sYW5nIjoiMiIsInRpdGxlIjoiXHUzMGQxXHUzMGI5XHUzMGJmIChQYXN0YSkiLCJkZXNjcmlwdGlvbiI6IjxwPlx1MzA0Mlx1MzA2YVx1MzA1Zlx1MzA2Zlx1MzBkMVx1MzBiOVx1MzBiZlx1MzA0Y1x1NTkyN1x1NTk3ZFx1NzI2OVx1MzA2N1x1MzA0Mlx1MzA4YVx1ZmYwY1x1NmJjZVx1NjVlNVx1ZmYwY1x1NjY2OVx1NWZhMVx1OThlZlx1MzA2Ylx1MzBkMVx1MzBiOVx1MzBiZlx1MzA5Mlx1NGY1Y1x1MzA2M1x1MzA2Nlx1OThkZlx1MzA3OVx1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZVx1MzA0Mlx1MzA2YVx1MzA1Zlx1MzA2Zlx1MzBjOFx1MzBkZVx1MzBjOFx1MzBiZFx1MzBmY1x1MzBiOVx1ZmYwY1x1MzBhZlx1MzBlYVx1MzBmY1x1MzBlMFx1MzBiZFx1MzBmY1x1MzBiOVx1ZmYwY1x1MzBkMFx1MzBiOFx1MzBlYlx1MzBiZFx1MzBmY1x1MzBiOVx1MzA2ZSAzIFx1N2EyZVx1OTg1ZVx1MzA2ZVx1MzBkMVx1MzBiOVx1MzBiZlx1MzA5Mlx1NGY1Y1x1MzA4Ylx1MzA1M1x1MzA2OFx1MzA0Y1x1MzA2N1x1MzA0ZFx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD5OIFx1NjVlNVx1OTU5M1x1MzA2ZVx1NjY2OVx1NWZhMVx1OThlZlx1MzA2ZVx1NGU4OFx1NWI5YVx1MzA5Mlx1ODAwM1x1MzA0OFx1MzA4Ylx1MzA1M1x1MzA2OFx1MzA2Ylx1MzA1N1x1MzA1Zlx1ZmYwZVx1MzA1ZFx1MzA4Y1x1MzA1ZVx1MzA4Y1x1MzA2ZVx1NjVlNVx1MzA2YiAzIFx1N2EyZVx1OTg1ZVx1MzA2ZVx1MzBkMVx1MzBiOVx1MzBiZlx1MzA0Ylx1MzA4OSAxIFx1N2EyZVx1OTg1ZVx1MzA5Mlx1OTA3OFx1MzA3Nlx1ZmYwZVx1MzA1Zlx1MzA2MFx1MzA1N1x1ZmYwY1x1NTQwY1x1MzA1OFx1MzBkMVx1MzBiOVx1MzBiZlx1MzA0Y1x1N2Q5YVx1MzA0Zlx1MzA2OFx1OThmZFx1MzA0ZFx1MzA2Nlx1MzA1N1x1MzA3ZVx1MzA0Nlx1MzA2ZVx1MzA2N1x1ZmYwYzMgXHU2NWU1XHU0ZWU1XHU0ZTBhXHU5MDIzXHU3ZDlhXHUzMDU3XHUzMDY2XHU1NDBjXHUzMDU4XHUzMGQxXHUzMGI5XHUzMGJmXHUzMDkyXHU5MDc4XHUzMDkzXHUzMDY3XHUzMDZmXHUzMDQ0XHUzMDUxXHUzMDZhXHUzMDQ0XHVmZjBlXHUzMDdlXHUzMDVmXHVmZjBjTiBcdTY1ZTVcdTMwNmVcdTMwNDZcdTMwNjFcdTMwNmUgSyBcdTY1ZTVcdTUyMDZcdTMwNmVcdTMwZDFcdTMwYjlcdTMwYmZcdTMwNmZcdTMwNTlcdTMwNjdcdTMwNmJcdTZjN2FcdTMwODFcdTMwNjZcdTMwNDJcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+XHU1MTY1XHU1MjliXHUzMDY4XHUzMDU3XHUzMDY2IE4gXHUzMDZlXHU1MDI0XHUzMDY4XHVmZjBjSyBcdTY1ZTVcdTUyMDZcdTMwNmVcdTMwZDFcdTMwYjlcdTMwYmZcdTMwNmVcdTYwYzVcdTU4MzFcdTMwNGNcdTRlMGVcdTMwNDhcdTMwODlcdTMwOGNcdTMwNWZcdTMwNjhcdTMwNGRcdWZmMGNcdTY3NjFcdTRlZjZcdTMwOTJcdTMwN2ZcdTMwNWZcdTMwNTlcdTRlODhcdTViOWFcdTMwNGNcdTRmNTVcdTkwMWFcdTMwOGFcdTMwNDJcdTMwOGJcdTMwNGJcdTMwOTIgMTAwMDAgXHUzMDY3XHU1MjcyXHUzMDYzXHUzMDVmXHU0ZjU5XHUzMDhhXHUzMDkyXHU2YzQyXHUzMDgxXHUzMDhiXHUzMGQ3XHUzMGVkXHUzMGIwXHUzMGU5XHUzMGUwXHUzMDkyXHU0ZjVjXHU2MjEwXHUzMDViXHUzMDg4XHVmZjBlPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdTUxNjVcdTUyOWJcdTMwNmYgSyArIDEgXHU4ODRjXHUzMDRiXHUzMDg5XHUzMDZhXHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPjEgXHU4ODRjXHU3NmVlXHUzMDZiXHUzMDZmIDIgXHUzMDY0XHUzMDZlXHU2NTc0XHU2NTcwIE4sIEsgKDMgXHUyMjY2IE4gXHUyMjY2IDEwMFx1ZmYwYzEgXHUyMjY2IEsgXHUyMjY2IE4pIFx1MzA0Y1x1N2E3YVx1NzY3ZFx1MzA5Mlx1NTMzYVx1NTIwN1x1MzA4YVx1MzA2OFx1MzA1N1x1MzA2Nlx1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD4xICsgaSBcdTg4NGNcdTc2ZWUgKDEgXHUyMjY2IGkgXHUyMjY2IEspIFx1MzA2Ylx1MzA2ZiAyIFx1MzA2NFx1MzA2ZVx1NjU3NFx1NjU3MCBBaSwgQmkgKDEgXHUyMjY2IEFpIFx1MjI2NiBOXHVmZjBjMSBcdTIyNjYgQmkgXHUyMjY2IDMpIFx1MzA0Y1x1N2E3YVx1NzY3ZFx1MzA5Mlx1NTMzYVx1NTIwN1x1MzA4YVx1MzA2OFx1MzA1N1x1MzA2Nlx1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZVx1MzA1M1x1MzA4Y1x1MzA2Zlx1ZmYwY0FpIFx1NjVlNVx1NzZlZVx1MzA2ZVx1MzBkMVx1MzBiOVx1MzBiZlx1MzA2Zlx1MzA1OVx1MzA2N1x1MzA2Ylx1NmM3YVx1MzA3ZVx1MzA2M1x1MzA2Nlx1MzA0YVx1MzA4YVx1ZmYwY0JpID0gMSBcdTMwNmVcdTMwNjhcdTMwNGRcdTMwNmZcdTMwYzhcdTMwZGVcdTMwYzhcdTMwYmRcdTMwZmNcdTMwYjlcdTMwNjdcdTMwNDJcdTMwOGFcdWZmMGNCaSA9IDIgXHUzMDZlXHUzMDY4XHUzMDRkXHUzMDZmXHUzMGFmXHUzMGVhXHUzMGZjXHUzMGUwXHUzMGJkXHUzMGZjXHUzMGI5XHUzMDY3XHUzMDQyXHUzMDhhXHVmZjBjQmkgPSAzIFx1MzA2ZVx1MzA2OFx1MzA0ZFx1MzA2Zlx1MzBkMFx1MzBiOFx1MzBlYlx1MzBiZFx1MzBmY1x1MzBiOVx1MzA2N1x1MzA0Mlx1MzA4Ylx1MzA1M1x1MzA2OFx1MzA5Mlx1ODg2OFx1MzA1OVx1ZmYwZUFpICgxIFx1MjI2NiBpIFx1MjI2NiBLKSBcdTMwNmZcdTUxNjhcdTMwNjZcdTc1NzBcdTMwNmFcdTMwOGJcdWZmMGVcdTRlMGVcdTMwNDhcdTMwODlcdTMwOGNcdTMwOGJcdTUxNjVcdTUyOWJcdTMwYzdcdTMwZmNcdTMwYmZcdTMwNmJcdTMwNGFcdTMwNDRcdTMwNjZcdWZmMGNcdTY3NjFcdTRlZjZcdTMwOTJcdTMwN2ZcdTMwNWZcdTMwNTlcdTRlODhcdTViOWFcdTMwNmYgMSBcdTkwMWFcdTMwOGFcdTRlZTVcdTRlMGFcdTMwNDJcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNGNcdTRmZGRcdThhM2NcdTMwNTVcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGU8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdTY3NjFcdTRlZjZcdTMwOTJcdTMwN2ZcdTMwNWZcdTMwNTlcdTRlODhcdTViOWFcdTMwNGNcdTRmNTVcdTkwMWFcdTMwOGFcdTMwNDJcdTMwOGJcdTMwNGJcdTMwOTIgMTAwMDAgXHUzMDY3XHU1MjcyXHUzMDYzXHUzMDVmXHU0ZjU5XHUzMDhhXHUzMDkyIDEgXHU4ODRjXHUzMDY3XHU1MWZhXHU1MjliXHUzMDViXHUzMDg4XHVmZjBlPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1Yzc3Y1x1YmNmOFx1YzViNCJ9XQ==