시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 353 137 100 41.667%

문제

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

상근이는 앞으로 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+XHViNzdjXHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgQjxzdWI+aTxcL3N1Yj4gPSAxXHVjNzc0XHViYTc0IFx1ZDFhMFx1YjljOFx1ZDFhMCBcdWMxOGNcdWMyYTQsIDJcdWM3NzRcdWJhNzQgXHVkMDZjXHViOWJjIFx1YzE4Y1x1YzJhNCwgM1x1Yzc3NFx1YmE3NCBcdWJjMTRcdWM5YzggXHVjMThjXHVjMmE0XHVjNzc0XHViMmU0LiBBaVx1YjI5NCBcdWJhYThcdWI0NTAgXHViMmU0XHViOTc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWMxMzhcdWM2YjggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjYzRcdWQ2OGRcdWM3NTggXHVjMjE4XHViOTdjIDEwMDAwXHVjNzNjXHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cclxuXHRcdWM2MDhcdWM4MWNcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1Y2QxZCA2XHVhYzAwXHVjOWMwXHVhYzAwIFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0MSwyLDEsMiwxPFwvcD5cclxuPHA+XHJcblx0MSwyLDEsMiwyPFwvcD5cclxuPHA+XHJcblx0MSwyLDEsMiwzPFwvcD5cclxuPHA+XHJcblx0MSwzLDEsMiwxPFwvcD5cclxuPHA+XHJcblx0MSwzLDEsMiwyPFwvcD5cclxuPHA+XHJcblx0MSwzLDEsMiwzPFwvcD5cclxuXHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTU0NiIsInByb2JsZW1fbGFuZyI6IjIiLCJ0aXRsZSI6Ilx1MzBkMVx1MzBiOVx1MzBiZiAoUGFzdGEpIiwiZGVzY3JpcHRpb24iOiI8cD5cdTMwNDJcdTMwNmFcdTMwNWZcdTMwNmZcdTMwZDFcdTMwYjlcdTMwYmZcdTMwNGNcdTU5MjdcdTU5N2RcdTcyNjlcdTMwNjdcdTMwNDJcdTMwOGFcdWZmMGNcdTZiY2VcdTY1ZTVcdWZmMGNcdTY2NjlcdTVmYTFcdTk4ZWZcdTMwNmJcdTMwZDFcdTMwYjlcdTMwYmZcdTMwOTJcdTRmNWNcdTMwNjNcdTMwNjZcdTk4ZGZcdTMwNzlcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdTMwNDJcdTMwNmFcdTMwNWZcdTMwNmZcdTMwYzhcdTMwZGVcdTMwYzhcdTMwYmRcdTMwZmNcdTMwYjlcdWZmMGNcdTMwYWZcdTMwZWFcdTMwZmNcdTMwZTBcdTMwYmRcdTMwZmNcdTMwYjlcdWZmMGNcdTMwZDBcdTMwYjhcdTMwZWJcdTMwYmRcdTMwZmNcdTMwYjlcdTMwNmUgMyBcdTdhMmVcdTk4NWVcdTMwNmVcdTMwZDFcdTMwYjlcdTMwYmZcdTMwOTJcdTRmNWNcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNGNcdTMwNjdcdTMwNGRcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+TiBcdTY1ZTVcdTk1OTNcdTMwNmVcdTY2NjlcdTVmYTFcdTk4ZWZcdTMwNmVcdTRlODhcdTViOWFcdTMwOTJcdTgwMDNcdTMwNDhcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNmJcdTMwNTdcdTMwNWZcdWZmMGVcdTMwNWRcdTMwOGNcdTMwNWVcdTMwOGNcdTMwNmVcdTY1ZTVcdTMwNmIgMyBcdTdhMmVcdTk4NWVcdTMwNmVcdTMwZDFcdTMwYjlcdTMwYmZcdTMwNGJcdTMwODkgMSBcdTdhMmVcdTk4NWVcdTMwOTJcdTkwNzhcdTMwNzZcdWZmMGVcdTMwNWZcdTMwNjBcdTMwNTdcdWZmMGNcdTU0MGNcdTMwNThcdTMwZDFcdTMwYjlcdTMwYmZcdTMwNGNcdTdkOWFcdTMwNGZcdTMwNjhcdTk4ZmRcdTMwNGRcdTMwNjZcdTMwNTdcdTMwN2VcdTMwNDZcdTMwNmVcdTMwNjdcdWZmMGMzIFx1NjVlNVx1NGVlNVx1NGUwYVx1OTAyM1x1N2Q5YVx1MzA1N1x1MzA2Nlx1NTQwY1x1MzA1OFx1MzBkMVx1MzBiOVx1MzBiZlx1MzA5Mlx1OTA3OFx1MzA5M1x1MzA2N1x1MzA2Zlx1MzA0NFx1MzA1MVx1MzA2YVx1MzA0NFx1ZmYwZVx1MzA3ZVx1MzA1Zlx1ZmYwY04gXHU2NWU1XHUzMDZlXHUzMDQ2XHUzMDYxXHUzMDZlIEsgXHU2NWU1XHU1MjA2XHUzMDZlXHUzMGQxXHUzMGI5XHUzMGJmXHUzMDZmXHUzMDU5XHUzMDY3XHUzMDZiXHU2YzdhXHUzMDgxXHUzMDY2XHUzMDQyXHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1NTE2NVx1NTI5Ylx1MzA2OFx1MzA1N1x1MzA2NiBOIFx1MzA2ZVx1NTAyNFx1MzA2OFx1ZmYwY0sgXHU2NWU1XHU1MjA2XHUzMDZlXHUzMGQxXHUzMGI5XHUzMGJmXHUzMDZlXHU2MGM1XHU1ODMxXHUzMDRjXHU0ZTBlXHUzMDQ4XHUzMDg5XHUzMDhjXHUzMDVmXHUzMDY4XHUzMDRkXHVmZjBjXHU2NzYxXHU0ZWY2XHUzMDkyXHUzMDdmXHUzMDVmXHUzMDU5XHU0ZTg4XHU1YjlhXHUzMDRjXHU0ZjU1XHU5MDFhXHUzMDhhXHUzMDQyXHUzMDhiXHUzMDRiXHUzMDkyIDEwMDAwIFx1MzA2N1x1NTI3Mlx1MzA2M1x1MzA1Zlx1NGY1OVx1MzA4YVx1MzA5Mlx1NmM0Mlx1MzA4MVx1MzA4Ylx1MzBkN1x1MzBlZFx1MzBiMFx1MzBlOVx1MzBlMFx1MzA5Mlx1NGY1Y1x1NjIxMFx1MzA1Ylx1MzA4OFx1ZmYwZTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHU1MTY1XHU1MjliXHUzMDZmIEsgKyAxIFx1ODg0Y1x1MzA0Ylx1MzA4OVx1MzA2YVx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD4xIFx1ODg0Y1x1NzZlZVx1MzA2Ylx1MzA2ZiAyIFx1MzA2NFx1MzA2ZVx1NjU3NFx1NjU3MCBOLCBLICgzIFx1MjI2NiBOIFx1MjI2NiAxMDBcdWZmMGMxIFx1MjI2NiBLIFx1MjI2NiBOKSBcdTMwNGNcdTdhN2FcdTc2N2RcdTMwOTJcdTUzM2FcdTUyMDdcdTMwOGFcdTMwNjhcdTMwNTdcdTMwNjZcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+MSArIGkgXHU4ODRjXHU3NmVlICgxIFx1MjI2NiBpIFx1MjI2NiBLKSBcdTMwNmJcdTMwNmYgMiBcdTMwNjRcdTMwNmVcdTY1NzRcdTY1NzAgQWksIEJpICgxIFx1MjI2NiBBaSBcdTIyNjYgTlx1ZmYwYzEgXHUyMjY2IEJpIFx1MjI2NiAzKSBcdTMwNGNcdTdhN2FcdTc2N2RcdTMwOTJcdTUzM2FcdTUyMDdcdTMwOGFcdTMwNjhcdTMwNTdcdTMwNjZcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdTMwNTNcdTMwOGNcdTMwNmZcdWZmMGNBaSBcdTY1ZTVcdTc2ZWVcdTMwNmVcdTMwZDFcdTMwYjlcdTMwYmZcdTMwNmZcdTMwNTlcdTMwNjdcdTMwNmJcdTZjN2FcdTMwN2VcdTMwNjNcdTMwNjZcdTMwNGFcdTMwOGFcdWZmMGNCaSA9IDEgXHUzMDZlXHUzMDY4XHUzMDRkXHUzMDZmXHUzMGM4XHUzMGRlXHUzMGM4XHUzMGJkXHUzMGZjXHUzMGI5XHUzMDY3XHUzMDQyXHUzMDhhXHVmZjBjQmkgPSAyIFx1MzA2ZVx1MzA2OFx1MzA0ZFx1MzA2Zlx1MzBhZlx1MzBlYVx1MzBmY1x1MzBlMFx1MzBiZFx1MzBmY1x1MzBiOVx1MzA2N1x1MzA0Mlx1MzA4YVx1ZmYwY0JpID0gMyBcdTMwNmVcdTMwNjhcdTMwNGRcdTMwNmZcdTMwZDBcdTMwYjhcdTMwZWJcdTMwYmRcdTMwZmNcdTMwYjlcdTMwNjdcdTMwNDJcdTMwOGJcdTMwNTNcdTMwNjhcdTMwOTJcdTg4NjhcdTMwNTlcdWZmMGVBaSAoMSBcdTIyNjYgaSBcdTIyNjYgSykgXHUzMDZmXHU1MTY4XHUzMDY2XHU3NTcwXHUzMDZhXHUzMDhiXHVmZjBlXHU0ZTBlXHUzMDQ4XHUzMDg5XHUzMDhjXHUzMDhiXHU1MTY1XHU1MjliXHUzMGM3XHUzMGZjXHUzMGJmXHUzMDZiXHUzMDRhXHUzMDQ0XHUzMDY2XHVmZjBjXHU2NzYxXHU0ZWY2XHUzMDkyXHUzMDdmXHUzMDVmXHUzMDU5XHU0ZTg4XHU1YjlhXHUzMDZmIDEgXHU5MDFhXHUzMDhhXHU0ZWU1XHU0ZTBhXHUzMDQyXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDRjXHU0ZmRkXHU4YTNjXHUzMDU1XHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHU2NzYxXHU0ZWY2XHUzMDkyXHUzMDdmXHUzMDVmXHUzMDU5XHU0ZTg4XHU1YjlhXHUzMDRjXHU0ZjU1XHU5MDFhXHUzMDhhXHUzMDQyXHUzMDhiXHUzMDRiXHUzMDkyIDEwMDAwIFx1MzA2N1x1NTI3Mlx1MzA2M1x1MzA1Zlx1NGY1OVx1MzA4YVx1MzA5MiAxIFx1ODg0Y1x1MzA2N1x1NTFmYVx1NTI5Ylx1MzA1Ylx1MzA4OFx1ZmYwZTxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM3N2NcdWJjZjhcdWM1YjQifV0=