시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB91245135851.884%

문제

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

상근이는 앞으로 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

예제 입력 2

20 5
10 2
4 3
12 1
13 2
9 1

예제 출력 2

2640

힌트

예제 1의 경우에는 총 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
W3sicHJvYmxlbV9pZCI6IjU1NDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMGNcdWMyYTRcdWQwYzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWI5ZTRcdWM3N2MgXHVjODAwXHViMTQxXHVjNzNjXHViODVjIFx1ZDMwY1x1YzJhNFx1ZDBjMFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWM1YjQgXHViYTM5XHViMjk0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVkMzBjXHVjMmE0XHVkMGMwXHViMjk0IFx1Y2QxZCBcdWMxMzggXHVjODg1XHViOTU4XHViODVjIFx1ZDFhMFx1YjljOFx1ZDFhMCBcdWMxOGNcdWMyYTQsIFx1ZDA2Y1x1YjliYyBcdWMxOGNcdWMyYTQsIFx1YmMxNFx1YzljOCBcdWMxOGNcdWMyYTRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM1NWVcdWM3M2NcdWI4NWMgTlx1Yzc3YyBcdWIzZDlcdWM1NDggXHViYTM5XHVjNzQ0IFx1ZDMwY1x1YzJhNFx1ZDBjMFx1Yjk3YyBcdWFjYzRcdWQ2OGRcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWI5ZTRcdWM3N2MgXHViOWU0XHVjNzdjIFx1YzEzOCBcdWM4ODVcdWI5NThcdWM3NTggXHVkMzBjXHVjMmE0XHVkMGMwIFx1YzkxMSBcdWQ1NWMgXHVjODg1XHViOTU4XHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVhYzE5XHVjNzQwIFx1ZDMwY1x1YzJhNFx1ZDBjMFx1Yjk3YyBcdWFjYzRcdWMxOGRcdWQ1NzRcdWMxMWMgXHViYTM5XHVjNzNjXHViYTc0IFx1YzljOFx1YjgyNFx1YmM4NFx1YjliNCBcdWMyMTggXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgM1x1Yzc3YyBcdWM3NzRcdWMwYzEgXHVjNWYwXHVjMThkXHVkNTc0XHVjMTFjIFx1YWMxOVx1Yzc0MCBcdWQzMGNcdWMyYTRcdWQwYzBcdWI5N2MgXHViYTM5XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNjEwLCBOXHVjNzdjIFx1YzkxMSBLXHVjNzdjXHVjNWQwIFx1YmEzOVx1Yzc0NCBcdWQzMGNcdWMyYTRcdWQwYzBcdWIyOTQgXHViYmY4XHViOWFjIFx1YzgxNVx1ZDU3NFx1YjQ1MFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+Tlx1YWNmYyBLXHVjNzdjXHVjNWQwIFx1YmEzOVx1Yzc0NCBcdWQzMGNcdWMyYTRcdWQwYzBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhYzAwXHViMmE1XHVkNTVjIFx1YWNjNFx1ZDY4ZFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjZmMgS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgzICZsZTsgTiAmbGU7IDEwMCwgMSAmbGU7IEsgJmxlOyBOKTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIEtcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0LCBcdWJiZjhcdWI5YWMgXHVkMzBjXHVjMmE0XHVkMGMwXHViOTdjIFx1YzgxNVx1ZDU3NFx1YjE5M1x1Yzc0MCBcdWIwYTBcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YzgxNVx1YmNmNFx1YjI5NCBBPHN1Yj5pPFwvc3ViPiBCPHN1Yj5pPFwvc3ViPlx1YzY0MCBcdWFjMTlcdWM3NDAgXHVkNjE1XHVjMmRkXHVjNzc0XHViYTcwLCBBPHN1Yj5pPFwvc3ViPlx1Yzc3Y1x1YzVkMCBcdWJhMzlcdWM3NDQgXHVkMzBjXHVjMmE0XHVkMGMwXHViMjk0IEI8c3ViPmk8XC9zdWI+XHViNzdjXHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC4gXHVjNzc0XHViNTRjLCBCPHN1Yj5pPFwvc3ViPiA9IDFcdWM3NzRcdWJhNzQgXHVkMWEwXHViOWM4XHVkMWEwIFx1YzE4Y1x1YzJhNCwgMlx1Yzc3NFx1YmE3NCBcdWQwNmNcdWI5YmMgXHVjMThjXHVjMmE0LCAzXHVjNzc0XHViYTc0IFx1YmMxNFx1YzljOCBcdWMxOGNcdWMyYTRcdWM3NzRcdWIyZTQuIEE8c3ViPmk8XC9zdWI+XHViMjk0IFx1YmFhOFx1YjQ1MCBcdWIyZTRcdWI5NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YzEzOFx1YzZiOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNjNFx1ZDY4ZFx1Yzc1OCBcdWMyMThcdWI5N2MgMTAwMDBcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YzYwOFx1YzgxYyAxXHVjNzU4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWNkMWQgNlx1YWMwMFx1YzljMFx1YWMwMCBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MSwyLDEsMiwxPFwvbGk+XHJcblx0PGxpPjEsMiwxLDIsMjxcL2xpPlxyXG5cdDxsaT4xLDIsMSwyLDM8XC9saT5cclxuXHQ8bGk+MSwzLDEsMiwxPFwvbGk+XHJcblx0PGxpPjEsMywxLDIsMjxcL2xpPlxyXG5cdDxsaT4xLDMsMSwyLDM8XC9saT5cclxuPFwvdWw+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNTU0NiIsInByb2JsZW1fbGFuZyI6IjIiLCJ0aXRsZSI6Ilx1MzBkMVx1MzBiOVx1MzBiZiAoUGFzdGEpIiwiZGVzY3JpcHRpb24iOiI8cD5cdTMwNDJcdTMwNmFcdTMwNWZcdTMwNmZcdTMwZDFcdTMwYjlcdTMwYmZcdTMwNGNcdTU5MjdcdTU5N2RcdTcyNjlcdTMwNjdcdTMwNDJcdTMwOGFcdWZmMGNcdTZiY2VcdTY1ZTVcdWZmMGNcdTY2NjlcdTVmYTFcdTk4ZWZcdTMwNmJcdTMwZDFcdTMwYjlcdTMwYmZcdTMwOTJcdTRmNWNcdTMwNjNcdTMwNjZcdTk4ZGZcdTMwNzlcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdTMwNDJcdTMwNmFcdTMwNWZcdTMwNmZcdTMwYzhcdTMwZGVcdTMwYzhcdTMwYmRcdTMwZmNcdTMwYjlcdWZmMGNcdTMwYWZcdTMwZWFcdTMwZmNcdTMwZTBcdTMwYmRcdTMwZmNcdTMwYjlcdWZmMGNcdTMwZDBcdTMwYjhcdTMwZWJcdTMwYmRcdTMwZmNcdTMwYjlcdTMwNmUgMyBcdTdhMmVcdTk4NWVcdTMwNmVcdTMwZDFcdTMwYjlcdTMwYmZcdTMwOTJcdTRmNWNcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNGNcdTMwNjdcdTMwNGRcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+TiBcdTY1ZTVcdTk1OTNcdTMwNmVcdTY2NjlcdTVmYTFcdTk4ZWZcdTMwNmVcdTRlODhcdTViOWFcdTMwOTJcdTgwMDNcdTMwNDhcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNmJcdTMwNTdcdTMwNWZcdWZmMGVcdTMwNWRcdTMwOGNcdTMwNWVcdTMwOGNcdTMwNmVcdTY1ZTVcdTMwNmIgMyBcdTdhMmVcdTk4NWVcdTMwNmVcdTMwZDFcdTMwYjlcdTMwYmZcdTMwNGJcdTMwODkgMSBcdTdhMmVcdTk4NWVcdTMwOTJcdTkwNzhcdTMwNzZcdWZmMGVcdTMwNWZcdTMwNjBcdTMwNTdcdWZmMGNcdTU0MGNcdTMwNThcdTMwZDFcdTMwYjlcdTMwYmZcdTMwNGNcdTdkOWFcdTMwNGZcdTMwNjhcdTk4ZmRcdTMwNGRcdTMwNjZcdTMwNTdcdTMwN2VcdTMwNDZcdTMwNmVcdTMwNjdcdWZmMGMzIFx1NjVlNVx1NGVlNVx1NGUwYVx1OTAyM1x1N2Q5YVx1MzA1N1x1MzA2Nlx1NTQwY1x1MzA1OFx1MzBkMVx1MzBiOVx1MzBiZlx1MzA5Mlx1OTA3OFx1MzA5M1x1MzA2N1x1MzA2Zlx1MzA0NFx1MzA1MVx1MzA2YVx1MzA0NFx1ZmYwZVx1MzA3ZVx1MzA1Zlx1ZmYwY04gXHU2NWU1XHUzMDZlXHUzMDQ2XHUzMDYxXHUzMDZlIEsgXHU2NWU1XHU1MjA2XHUzMDZlXHUzMGQxXHUzMGI5XHUzMGJmXHUzMDZmXHUzMDU5XHUzMDY3XHUzMDZiXHU2YzdhXHUzMDgxXHUzMDY2XHUzMDQyXHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1NTE2NVx1NTI5Ylx1MzA2OFx1MzA1N1x1MzA2NiBOIFx1MzA2ZVx1NTAyNFx1MzA2OFx1ZmYwY0sgXHU2NWU1XHU1MjA2XHUzMDZlXHUzMGQxXHUzMGI5XHUzMGJmXHUzMDZlXHU2MGM1XHU1ODMxXHUzMDRjXHU0ZTBlXHUzMDQ4XHUzMDg5XHUzMDhjXHUzMDVmXHUzMDY4XHUzMDRkXHVmZjBjXHU2NzYxXHU0ZWY2XHUzMDkyXHUzMDdmXHUzMDVmXHUzMDU5XHU0ZTg4XHU1YjlhXHUzMDRjXHU0ZjU1XHU5MDFhXHUzMDhhXHUzMDQyXHUzMDhiXHUzMDRiXHUzMDkyIDEwMDAwIFx1MzA2N1x1NTI3Mlx1MzA2M1x1MzA1Zlx1NGY1OVx1MzA4YVx1MzA5Mlx1NmM0Mlx1MzA4MVx1MzA4Ylx1MzBkN1x1MzBlZFx1MzBiMFx1MzBlOVx1MzBlMFx1MzA5Mlx1NGY1Y1x1NjIxMFx1MzA1Ylx1MzA4OFx1ZmYwZTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHU1MTY1XHU1MjliXHUzMDZmIEsgKyAxIFx1ODg0Y1x1MzA0Ylx1MzA4OVx1MzA2YVx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD4xIFx1ODg0Y1x1NzZlZVx1MzA2Ylx1MzA2ZiAyIFx1MzA2NFx1MzA2ZVx1NjU3NFx1NjU3MCBOLCBLICgzIFx1MjI2NiBOIFx1MjI2NiAxMDBcdWZmMGMxIFx1MjI2NiBLIFx1MjI2NiBOKSBcdTMwNGNcdTdhN2FcdTc2N2RcdTMwOTJcdTUzM2FcdTUyMDdcdTMwOGFcdTMwNjhcdTMwNTdcdTMwNjZcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+MSArIGkgXHU4ODRjXHU3NmVlICgxIFx1MjI2NiBpIFx1MjI2NiBLKSBcdTMwNmJcdTMwNmYgMiBcdTMwNjRcdTMwNmVcdTY1NzRcdTY1NzAgQTxzdWI+aTxcL3N1Yj4sIEI8c3ViPmk8XC9zdWI+ICgxIFx1MjI2NiBBPHN1Yj5pPFwvc3ViPiBcdTIyNjYgTlx1ZmYwYzEgXHUyMjY2IEI8c3ViPmk8XC9zdWI+IFx1MjI2NiAzKSBcdTMwNGNcdTdhN2FcdTc2N2RcdTMwOTJcdTUzM2FcdTUyMDdcdTMwOGFcdTMwNjhcdTMwNTdcdTMwNjZcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdTMwNTNcdTMwOGNcdTMwNmZcdWZmMGNBPHN1Yj5pPFwvc3ViPiBcdTY1ZTVcdTc2ZWVcdTMwNmVcdTMwZDFcdTMwYjlcdTMwYmZcdTMwNmZcdTMwNTlcdTMwNjdcdTMwNmJcdTZjN2FcdTMwN2VcdTMwNjNcdTMwNjZcdTMwNGFcdTMwOGFcdWZmMGNCPHN1Yj5pPFwvc3ViPiA9IDEgXHUzMDZlXHUzMDY4XHUzMDRkXHUzMDZmXHUzMGM4XHUzMGRlXHUzMGM4XHUzMGJkXHUzMGZjXHUzMGI5XHUzMDY3XHUzMDQyXHUzMDhhXHVmZjBjQjxzdWI+aTxcL3N1Yj4gPSAyIFx1MzA2ZVx1MzA2OFx1MzA0ZFx1MzA2Zlx1MzBhZlx1MzBlYVx1MzBmY1x1MzBlMFx1MzBiZFx1MzBmY1x1MzBiOVx1MzA2N1x1MzA0Mlx1MzA4YVx1ZmYwY0I8c3ViPmk8XC9zdWI+ID0gMyBcdTMwNmVcdTMwNjhcdTMwNGRcdTMwNmZcdTMwZDBcdTMwYjhcdTMwZWJcdTMwYmRcdTMwZmNcdTMwYjlcdTMwNjdcdTMwNDJcdTMwOGJcdTMwNTNcdTMwNjhcdTMwOTJcdTg4NjhcdTMwNTlcdWZmMGVBPHN1Yj5pPFwvc3ViPiAoMSBcdTIyNjYgaSBcdTIyNjYgSykgXHUzMDZmXHU1MTY4XHUzMDY2XHU3NTcwXHUzMDZhXHUzMDhiXHVmZjBlXHU0ZTBlXHUzMDQ4XHUzMDg5XHUzMDhjXHUzMDhiXHU1MTY1XHU1MjliXHUzMGM3XHUzMGZjXHUzMGJmXHUzMDZiXHUzMDRhXHUzMDQ0XHUzMDY2XHVmZjBjXHU2NzYxXHU0ZWY2XHUzMDkyXHUzMDdmXHUzMDVmXHUzMDU5XHU0ZTg4XHU1YjlhXHUzMDZmIDEgXHU5MDFhXHUzMDhhXHU0ZWU1XHU0ZTBhXHUzMDQyXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDRjXHU0ZmRkXHU4YTNjXHUzMDU1XHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHU2NzYxXHU0ZWY2XHUzMDkyXHUzMDdmXHUzMDVmXHUzMDU5XHU0ZTg4XHU1YjlhXHUzMDRjXHU0ZjU1XHU5MDFhXHUzMDhhXHUzMDQyXHUzMDhiXHUzMDRiXHUzMDkyIDEwMDAwIFx1MzA2N1x1NTI3Mlx1MzA2M1x1MzA1Zlx1NGY1OVx1MzA4YVx1MzA5MiAxIFx1ODg0Y1x1MzA2N1x1NTFmYVx1NTI5Ylx1MzA1Ylx1MzA4OFx1ZmYwZTxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdTUxNjVcdTUxZmFcdTUyOWJcdTRmOGIgMSBcdTMwNmJcdTMwNGFcdTMwNDRcdTMwNjZcdWZmMGNcdTMwNDJcdTMwNmFcdTMwNWZcdTMwNmYgNSBcdTY1ZTVcdTk1OTNcdTMwNmVcdTRlODhcdTViOWFcdTMwOTJcdTgwMDNcdTMwNDhcdTMwOGJcdWZmMGUxIFx1NjVlNVx1NzZlZVx1MzA2OCAzIFx1NjVlNVx1NzZlZVx1MzA2Zlx1MzBjOFx1MzBkZVx1MzBjOFx1MzBiZFx1MzBmY1x1MzBiOVx1MzA2N1x1MzA0Mlx1MzA4YVx1ZmYwYzQgXHU2NWU1XHU3NmVlXHUzMDZmXHUzMGFmXHUzMGVhXHUzMGZjXHUzMGUwXHUzMGJkXHUzMGZjXHUzMGI5XHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlXHUzMDdlXHUzMDVmXHVmZjBjMyBcdTY1ZTVcdTRlZTVcdTRlMGFcdTkwMjNcdTdkOWFcdTMwNTdcdTMwNjZcdTU0MGNcdTMwNThcdTMwZDFcdTMwYjlcdTMwYmZcdTMwOTJcdTkwNzhcdTMwOTNcdTMwNjdcdTMwNmZcdTMwNDRcdTMwNTFcdTMwNmFcdTMwNDRcdWZmMGVcdTMwNTNcdTMwOGNcdTMwODlcdTMwNmVcdTY3NjFcdTRlZjZcdTMwOTJcdTMwN2ZcdTMwNWZcdTMwNTlcdTRlODhcdTViOWFcdTMwNmYgNiBcdTkwMWFcdTMwOGFcdTMwNDJcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOjUwJTtcIj5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD4mbmJzcDs8XC90aD5cclxuXHRcdFx0PHRoPiZuYnNwOzFcdTY1ZTVcdTc2ZWUmbmJzcDs8XC90aD5cclxuXHRcdFx0PHRoPiZuYnNwOzJcdTY1ZTVcdTc2ZWUmbmJzcDs8XC90aD5cclxuXHRcdFx0PHRoPiZuYnNwOzNcdTY1ZTVcdTc2ZWUmbmJzcDs8XC90aD5cclxuXHRcdFx0PHRoPiZuYnNwOzRcdTY1ZTVcdTc2ZWUmbmJzcDs8XC90aD5cclxuXHRcdFx0PHRoPiZuYnNwOzVcdTY1ZTVcdTc2ZWUmbmJzcDs8XC90aD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+XHU0ZTg4XHU1YjlhIDEmbmJzcDsmbmJzcDsmbmJzcDs8XC90aD5cclxuXHRcdFx0PHRkIGFsaWduPVwiY2VudGVyXCI+MTxcL3RkPlxyXG5cdFx0XHQ8dGQgYWxpZ249XCJjZW50ZXJcIj4yPFwvdGQ+XHJcblx0XHRcdDx0ZCBhbGlnbj1cImNlbnRlclwiPjE8XC90ZD5cclxuXHRcdFx0PHRkIGFsaWduPVwiY2VudGVyXCI+MjxcL3RkPlxyXG5cdFx0XHQ8dGQgYWxpZ249XCJjZW50ZXJcIj4xPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPlx1NGU4OFx1NWI5YSAyJm5ic3A7Jm5ic3A7Jm5ic3A7PFwvdGg+XHJcblx0XHRcdDx0ZCBhbGlnbj1cImNlbnRlclwiPjE8XC90ZD5cclxuXHRcdFx0PHRkIGFsaWduPVwiY2VudGVyXCI+MjxcL3RkPlxyXG5cdFx0XHQ8dGQgYWxpZ249XCJjZW50ZXJcIj4xPFwvdGQ+XHJcblx0XHRcdDx0ZCBhbGlnbj1cImNlbnRlclwiPjI8XC90ZD5cclxuXHRcdFx0PHRkIGFsaWduPVwiY2VudGVyXCI+MjxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5cdTRlODhcdTViOWEgMyZuYnNwOyZuYnNwOyZuYnNwOzxcL3RoPlxyXG5cdFx0XHQ8dGQgYWxpZ249XCJjZW50ZXJcIj4xPFwvdGQ+XHJcblx0XHRcdDx0ZCBhbGlnbj1cImNlbnRlclwiPjI8XC90ZD5cclxuXHRcdFx0PHRkIGFsaWduPVwiY2VudGVyXCI+MTxcL3RkPlxyXG5cdFx0XHQ8dGQgYWxpZ249XCJjZW50ZXJcIj4yPFwvdGQ+XHJcblx0XHRcdDx0ZCBhbGlnbj1cImNlbnRlclwiPjM8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+XHU0ZTg4XHU1YjlhIDQmbmJzcDsmbmJzcDsmbmJzcDs8XC90aD5cclxuXHRcdFx0PHRkIGFsaWduPVwiY2VudGVyXCI+MTxcL3RkPlxyXG5cdFx0XHQ8dGQgYWxpZ249XCJjZW50ZXJcIj4zPFwvdGQ+XHJcblx0XHRcdDx0ZCBhbGlnbj1cImNlbnRlclwiPjE8XC90ZD5cclxuXHRcdFx0PHRkIGFsaWduPVwiY2VudGVyXCI+MjxcL3RkPlxyXG5cdFx0XHQ8dGQgYWxpZ249XCJjZW50ZXJcIj4xPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPlx1NGU4OFx1NWI5YSA1Jm5ic3A7Jm5ic3A7Jm5ic3A7PFwvdGg+XHJcblx0XHRcdDx0ZCBhbGlnbj1cImNlbnRlclwiPjE8XC90ZD5cclxuXHRcdFx0PHRkIGFsaWduPVwiY2VudGVyXCI+MzxcL3RkPlxyXG5cdFx0XHQ8dGQgYWxpZ249XCJjZW50ZXJcIj4xPFwvdGQ+XHJcblx0XHRcdDx0ZCBhbGlnbj1cImNlbnRlclwiPjI8XC90ZD5cclxuXHRcdFx0PHRkIGFsaWduPVwiY2VudGVyXCI+MjxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD5cdTRlODhcdTViOWEgNiZuYnNwOyZuYnNwOyZuYnNwOzxcL3RoPlxyXG5cdFx0XHQ8dGQgYWxpZ249XCJjZW50ZXJcIj4xPFwvdGQ+XHJcblx0XHRcdDx0ZCBhbGlnbj1cImNlbnRlclwiPjM8XC90ZD5cclxuXHRcdFx0PHRkIGFsaWduPVwiY2VudGVyXCI+MTxcL3RkPlxyXG5cdFx0XHQ8dGQgYWxpZ249XCJjZW50ZXJcIj4yPFwvdGQ+XHJcblx0XHRcdDx0ZCBhbGlnbj1cImNlbnRlclwiPjM8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcbjxwPlx1MzA1M1x1MzA2ZVx1ODg2OFx1MzA2N1x1MzA2Zlx1ZmYwYzEgXHUzMDZmXHUzMGM4XHUzMGRlXHUzMGM4XHUzMGJkXHUzMGZjXHUzMGI5XHUzMDkyXHVmZjBjMiBcdTMwNmZcdTMwYWZcdTMwZWFcdTMwZmNcdTMwZTBcdTMwYmRcdTMwZmNcdTMwYjlcdTMwOTJcdWZmMGMzIFx1MzA2Zlx1MzBkMFx1MzBiOFx1MzBlYlx1MzBiZFx1MzBmY1x1MzBiOVx1MzA5Mlx1ODg2OFx1MzA1OVx1ZmYwZTxcL3A+XHJcblxyXG48cD5cdTUxNjVcdTUxZmFcdTUyOWJcdTRmOGIgMiBcdTMwNmJcdTMwNGFcdTMwNDRcdTMwNjZcdWZmMGNcdTY3NjFcdTRlZjZcdTMwOTJcdTMwN2ZcdTMwNWZcdTMwNTlcdTRlODhcdTViOWFcdTMwNmZcdTUxNjhcdTkwZThcdTMwNjcgNDExMjY0MCBcdTkwMWFcdTMwOGFcdTMwNDJcdTMwOGJcdWZmMGVcdTMwNWRcdTMwOGNcdTMwOTIgMTAwMDAgXHUzMDY3XHU1MjcyXHUzMDYzXHUzMDVmXHU0ZjU5XHUzMDhhXHUzMDY3XHUzMDQyXHUzMDhiIDI2NDAgXHUzMDkyXHU1MWZhXHU1MjliXHUzMDU5XHUzMDhiXHVmZjBlPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJKYXBhbmVzZSJ9XQ==

출처

Olympiad > Japanese Olympiad in Informatics > Japanese Olympiad in Informatics Qualification Round > JOI 2011/2012 예선 4번