시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 119 38 15 48.387%

문제

일본 정보올림피아드 위원회는 일본 정보올림피아드(JOI)를 홍보하기 위해서 JOI로고를 모티브로 한 깃발을 만들었다. 깃발은 "좋은 깃발" 이어야 한다. "좋은 깃발"은 알파벳 J, O, I중 하나의 문자를 M행 N열 사각형 형태로 배치한 것으로, 아래 그림과 같이 배치되어 있는 곳이 깃발에 적어도 한 곳 있는 깃발이다.

다음은 "좋은 깃발"의 예이다.

다음은 "좋은 깃발"이 아닌 예이다.

일부 위치에는 이미 그 칸을 채울 문자가 정해져 있다. 이때, M, N이 주어졌을 때, 좋은 깃발을 만들 수 있는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 깃발의 크기 M과 N이 주어진다. (2 ≤ M, N ≤ 20)

다음 M개 줄에는 깃발의 모양인 N개 문자가 주어진다. 각 문자는 J, O, I, ?중 하나이다. J, O, I인 경우에는 i행 j열 위치의 문자가 이미 그 문자로 정해져 있는 뜻이고, ?는 아직 정해져 있지 않다는 뜻이다.

출력

첫째 줄에 "좋은 깃발"을 만들 수 있는 방법의 수를 100000으로 나눈 나머지를 출력한다.

예제 입력 1

2 3
??O
IIJ

예제 출력 1

4

힌트

W3sicHJvYmxlbV9pZCI6IjU1NTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJKT0kgXHVhZTQzXHViYzFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3N2NcdWJjZjggXHVjODE1XHViY2Y0XHVjNjJjXHViOWJjXHVkNTNjXHVjNTQ0XHViNGRjIFx1YzcwNFx1YzZkMFx1ZDY4Y1x1YjI5NCBcdWM3N2NcdWJjZjggXHVjODE1XHViY2Y0XHVjNjJjXHViOWJjXHVkNTNjXHVjNTQ0XHViNGRjKEpPSSlcdWI5N2MgXHVkNjRkXHViY2Y0XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBKT0lcdWI4NWNcdWFjZTBcdWI5N2MgXHViYWE4XHVkMmYwXHViZTBjXHViODVjIFx1ZDU1YyBcdWFlNDNcdWJjMWNcdWM3NDQgXHViOWNjXHViNGU0XHVjNWM4XHViMmU0LiBcdWFlNDNcdWJjMWNcdWM3NDAgJnF1b3Q7XHVjODhiXHVjNzQwIFx1YWU0M1x1YmMxYyZxdW90OyBcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiAmcXVvdDtcdWM4OGJcdWM3NDAgXHVhZTQzXHViYzFjJnF1b3Q7XHVjNzQwIFx1YzU0Y1x1ZDMwY1x1YmNiMyBKLCBPLCBJXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWJiMzhcdWM3OTBcdWI5N2MgTVx1ZDU4OSBOXHVjNWY0IFx1YzBhY1x1YWMwMVx1ZDYxNSBcdWQ2MTVcdWQwZGNcdWI4NWMgXHViYzMwXHVjZTU4XHVkNTVjIFx1YWM4M1x1YzczY1x1Yjg1YywgXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1YWNmYyBcdWFjMTlcdWM3NzQgXHViYzMwXHVjZTU4XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWFjZjNcdWM3NzQgXHVhZTQzXHViYzFjXHVjNWQwIFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NWMgXHVhY2YzIFx1Yzc4OFx1YjI5NCBcdWFlNDNcdWJjMWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9qb2kxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEwMHB4OyB3aWR0aDoxMDBweFwiIFwvPjxcL3A+XHJcblxyXG5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0Y1x1Yzc0MCAmcXVvdDtcdWM4OGJcdWM3NDAgXHVhZTQzXHViYzFjJnF1b3Q7XHVjNzU4IFx1YzYwOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuXHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2pvaTIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTQ4cHg7IHdpZHRoOjM0MHB4XCIgXC8+PFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHViMmU0XHVjNzRjXHVjNzQwICZxdW90O1x1Yzg4Ylx1Yzc0MCBcdWFlNDNcdWJjMWMmcXVvdDtcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzYwOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuXHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2pvaTMucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTQ4cHg7IHdpZHRoOjM0MHB4XCIgXC8+PFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHVjNzdjXHViZDgwIFx1YzcwNFx1Y2U1OFx1YzVkMFx1YjI5NCBcdWM3NzRcdWJiZjggXHVhZGY4IFx1Y2U3OFx1Yzc0NCBcdWNjNDRcdWM2YjggXHViYjM4XHVjNzkwXHVhYzAwIFx1YzgxNVx1ZDU3NFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjU0YywgTSwgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM4OGJcdWM3NDAgXHVhZTQzXHViYzFjXHVjNzQ0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWU0M1x1YmMxY1x1Yzc1OCBcdWQwNmNcdWFlMzAgTVx1YWNmYyBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBNLCBOICZsZTsgMjApPFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWU0M1x1YmMxY1x1Yzc1OCBcdWJhYThcdWM1OTFcdWM3NzggTlx1YWMxYyBcdWJiMzhcdWM3OTBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHViYjM4XHVjNzkwXHViMjk0IEosIE8sIEksID9cdWM5MTEgXHVkNTU4XHViMDk4XHVjNzc0XHViMmU0LiBKLCBPLCBJXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBpXHVkNTg5IGpcdWM1ZjQgXHVjNzA0XHVjZTU4XHVjNzU4IFx1YmIzOFx1Yzc5MFx1YWMwMCBcdWM3NzRcdWJiZjggXHVhZGY4IFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM4MTVcdWQ1NzRcdWM4MzggXHVjNzg4XHViMjk0IFx1YjczYlx1Yzc3NFx1YWNlMCwgP1x1YjI5NCBcdWM1NDRcdWM5YzEgXHVjODE1XHVkNTc0XHVjODM4IFx1Yzc4OFx1YzljMCBcdWM1NGFcdWIyZTRcdWIyOTQgXHViNzNiXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgJnF1b3Q7XHVjODhiXHVjNzQwIFx1YWU0M1x1YmMxYyZxdW90O1x1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIDEwMDAwMFx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9qb2k0LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI0NHB4OyB3aWR0aDozNDBweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1NTU5IiwicHJvYmxlbV9sYW5nIjoiMiIsInRpdGxlIjoiSk9JIFx1NjVkNyAoSk9JIEZsYWcpIiwiZGVzY3JpcHRpb24iOiI8cD5cdTMwYWFcdTMwZWFcdTMwZjNcdTMwZDRcdTMwYzNcdTMwYWZcdTY1ZTVcdTY3MmNcdTU5ZDRcdTU0ZTFcdTRmMWFcdTMwNjdcdTMwNmZcdWZmMGNcdTRlY2FcdTVlNzRcdTMwNmVcdTY1ZTVcdTY3MmNcdTYwYzVcdTU4MzFcdTMwYWFcdTMwZWFcdTMwZjNcdTMwZDRcdTMwYzNcdTMwYWYgKEpPSSkgXHUzMDkyXHU1YmEzXHU0ZjFkXHUzMDU5XHUzMDhiXHUzMDVmXHUzMDgxXHUzMDZiXHVmZjBjIEpPSSBcdTMwNmVcdTMwZWRcdTMwYjRcdTMwOTJcdTMwZTJcdTMwYzFcdTMwZmNcdTMwZDVcdTMwNmJcdTMwNTdcdTMwNWZcdTY1ZDdcdTMwOTJcdTRmNWNcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNmJcdTMwNmFcdTMwNjNcdTMwNWZcdWZmMGUgXHU2NWQ3XHUzMDZmXHUzMDBjXHU4MjZmXHUzMDQ0XHU2NWQ3XHUzMDBkXHUzMDY3XHUzMDZhXHUzMDUxXHUzMDhjXHUzMDcwXHUzMDZhXHUzMDg5XHUzMDZhXHUzMDQ0XHVmZjBlIFx1MzAwY1x1ODI2Zlx1MzA0NFx1NjVkN1x1MzAwZFx1MzA2OFx1MzA2Zlx1ZmYwY1x1MzBhMlx1MzBlYlx1MzBkNVx1MzBhMVx1MzBkOVx1MzBjM1x1MzBjOFx1MzA2ZSBKLCBPLCBJIFx1MzA2ZVx1MzA0NFx1MzA1YVx1MzA4Y1x1MzA0Ylx1MzA2ZVx1NjU4N1x1NWI1N1x1MzA5Mlx1ZmYwY1x1N2UyNiBNIFx1ODg0Y1x1ZmYwY1x1NmEyYSBOIFx1NTIxN1x1MzA2ZVx1OTU3N1x1NjViOVx1NWY2Mlx1NzJiNlx1MzA2Ylx1NGUyNlx1MzA3OVx1MzA1Zlx1MzA4Mlx1MzA2ZVx1MzA2N1x1ZmYwYyBKLCBPLCBJIFx1MzA0Y1x1NGVlNVx1NGUwYlx1MzA2ZVx1NTZmM1x1MzA2ZVx1MzA4OFx1MzA0Nlx1MzA2YiAoXHUzMDU5XHUzMDZhXHUzMDhmXHUzMDYxXHVmZjBjSiBcdTMwNmVcdTUzZjNcdTk2YTNcdTMwNmIgTyBcdTMwNGNcdWZmMGNcdTMwNWRcdTMwNmUgSiBcdTMwNmVcdTRlMGJcdTk2YTNcdTMwNmIgSSBcdTMwNGMpIFx1NGUyNlx1MzA5M1x1MzA2N1x1MzA0NFx1MzA4Ylx1N2I4N1x1NjI0MFx1MzA0Y1x1NjVkN1x1MzA2ZVx1NWMxMVx1MzA2YVx1MzA0Zlx1MzA2OFx1MzA4MiAxIFx1MzA0Ylx1NjI0MFx1MzA2Ylx1MzA0Mlx1MzA4Ylx1MzA4Mlx1MzA2ZVx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2pvaTEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTAwcHg7IHdpZHRoOjEwMHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1NGVlNVx1NGUwYlx1MzA2ZVx1NTZmM1x1MzA2Ylx1ZmYwY1x1MzAwY1x1ODI2Zlx1MzA0NFx1NjVkN1x1MzAwZFx1MzA2ZVx1NGY4Ylx1MzA5MiAyIFx1MzA2NFx1NzkzYVx1MzA1OVx1ZmYwZTxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2pvaTIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTQ4cHg7IHdpZHRoOjM0MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1NGVlNVx1NGUwYlx1MzA2ZVx1NTZmM1x1MzA2Ylx1ZmYwY1x1MzAwY1x1ODI2Zlx1MzA0NFx1NjVkN1x1MzAwZFx1MzA2N1x1MzA2Zlx1MzA2YVx1MzA0NFx1NGY4Ylx1MzA5MiAyIFx1MzA2NFx1NzkzYVx1MzA1OVx1ZmYwZTxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2pvaTMucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTQ4cHg7IG9wYWNpdHk6MC45OyB3aWR0aDozNDBweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdTMwNDRcdTMwN2UgTSwgTiBcdTMwNmVcdTUwMjRcdWZmMGNcdTMwNGFcdTMwODhcdTMwNzNcdTY1ZDdcdTMwNmVcdTRlMDBcdTkwZThcdTMwNmVcdTU4MzRcdTYyNDBcdTMwNmJcdTMwNjRcdTMwNDRcdTMwNjYgSiwgTywgSSBcdTMwNmVcdTMwNjlcdTMwNmVcdTY1ODdcdTViNTdcdTMwNmJcdTMwNTlcdTMwOGJcdTMwNGJcdTMwNGNcdTZjN2FcdTMwN2VcdTMwNjNcdTMwNjZcdTMwNGFcdTMwOGFcdWZmMGNcdTUxNjVcdTUyOWJcdTMwNjhcdTMwNTdcdTMwNjZcdTMwNWRcdTMwNmVcdTYwYzVcdTU4MzFcdTMwNGNcdTRlMGVcdTMwNDhcdTMwODlcdTMwOGNcdTMwOGJcdWZmMGUgXHU4MDAzXHUzMDQ4XHUzMDg5XHUzMDhjXHUzMDhiXHUzMDBjXHU4MjZmXHUzMDQ0XHU2NWQ3XHUzMDBkXHUzMDZmXHU0ZjU1XHU5MDFhXHUzMDhhXHUzMDQyXHUzMDhiXHUzMDRiXHUzMDkyXHU4YTA4XHU3Yjk3XHUzMDU3XHVmZjBjXHUzMDVkXHUzMDZlXHU2NTcwXHUzMDkyIDEwMDAwMCAoPTEwPHN1cD41PFwvc3VwPikgXHUzMDY3XHU1MjcyXHUzMDYzXHUzMDVmXHU0ZjU5XHUzMDhhXHUzMDkyXHU1MWZhXHU1MjliXHUzMDU5XHUzMDhiXHUzMGQ3XHUzMGVkXHUzMGIwXHUzMGU5XHUzMGUwXHUzMDkyXHU0ZjVjXHU2MjEwXHUzMDViXHUzMDg4XHVmZjBlPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdTUxNjVcdTUyOWJcdTMwNmYgMSArIE0gXHU4ODRjXHUzMDRiXHUzMDg5XHUzMDZhXHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPjEgXHU4ODRjXHU3NmVlXHUzMDZiXHUzMDZmXHU2NWQ3XHUzMDZlXHU1OTI3XHUzMDRkXHUzMDU1XHUzMDkyXHU4ODY4XHUzMDU5IDIgXHUzMDY0XHUzMDZlXHU2NTc0XHU2NTcwIE0sIE4gKDIgXHUyMjY2IE0gXHUyMjY2IDIwLCAyIFx1MjI2NiBOIFx1MjI2NiAyMCkgXHUzMDRjXHU3YTdhXHU3NjdkXHUzMDY3XHU1MzNhXHU1MjA3XHUzMDg5XHUzMDhjXHUzMDY2XHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPjEgKyBpIFx1ODg0Y1x1NzZlZSAoMSBcdTIyNjYgaSBcdTIyNjYgTSkgXHUzMDZiXHUzMDZmXHVmZjBjTiBcdTY1ODdcdTViNTdcdTMwNGJcdTMwODlcdTMwNmFcdTMwOGJcdTY1ODdcdTViNTdcdTUyMTdcdTMwNGNcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGUgXHU1NDA0XHU2NTg3XHU1YjU3XHUzMDZmIEosIE8sIEksID8gXHUzMDZlXHUzMDQ0XHUzMDVhXHUzMDhjXHUzMDRiXHUzMDY3XHUzMDQyXHUzMDhhXHVmZjBjIGogXHU2NTg3XHU1YjU3XHU3NmVlICgxIFx1MjI2NiBqIFx1MjI2NiBOKSBcdTMwNGMgSiwgTywgSSBcdTMwNmVcdTMwNDRcdTMwNWFcdTMwOGNcdTMwNGJcdTMwNjdcdTMwNDJcdTMwOGJcdTU4MzRcdTU0MDhcdTMwNmYgaSBcdTg4NGMgaiBcdTUyMTdcdTMwNmVcdTU4MzRcdTYyNDBcdTMwNmVcdTY1ODdcdTViNTdcdTMwNGNcdTMwNWRcdTMwOGNcdTMwNWVcdTMwOGMgSiwgTywgSSBcdTMwNmJcdTZjN2FcdTMwN2VcdTMwNjNcdTMwNjZcdTMwNDRcdTMwOGJcdTMwNTNcdTMwNjhcdWZmMGMgPyBcdTMwNjdcdTMwNDJcdTMwOGJcdTU4MzRcdTU0MDhcdTMwNmZcdTMwN2VcdTMwNjBcdTZjN2FcdTMwN2VcdTMwNjNcdTMwNjZcdTMwNDRcdTMwNmFcdTMwNDRcdTMwNTNcdTMwNjhcdTMwOTJcdTg4NjhcdTMwNTlcdWZmMGU8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdTgwMDNcdTMwNDhcdTMwODlcdTMwOGNcdTMwOGJcdTMwMGNcdTgyNmZcdTMwNDRcdTY1ZDdcdTMwMGRcdTMwNmVcdTUwMGJcdTY1NzBcdTMwOTIgMTAwMDAwICg9MTA8c3VwPjU8XC9zdXA+KSBcdTMwNjdcdTUyNzJcdTMwNjNcdTMwNWZcdTRmNTlcdTMwOGFcdTMwOTIgMSBcdTg4NGNcdTMwNjdcdTUxZmFcdTUyOWJcdTMwNWJcdTMwODhcdWZmMGU8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvam9pNC5wbmdcIiBzdHlsZT1cImhlaWdodDoyNDRweDsgb3BhY2l0eTowLjk7IHdpZHRoOjM0MHB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1Yzc3Y1x1YmNmOFx1YzViNCJ9XQ==