시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 97 27 9 47.368%

문제

일본 정보올림피아드 위원회는 일본 정보올림피아드(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+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTU1OSIsInByb2JsZW1fbGFuZyI6IjIiLCJ0aXRsZSI6IkpPSSBcdTY1ZDcgKEpPSSBGbGFnKSIsImRlc2NyaXB0aW9uIjoiPHA+XHUzMGFhXHUzMGVhXHUzMGYzXHUzMGQ0XHUzMGMzXHUzMGFmXHU2NWU1XHU2NzJjXHU1OWQ0XHU1NGUxXHU0ZjFhXHUzMDY3XHUzMDZmXHVmZjBjXHU0ZWNhXHU1ZTc0XHUzMDZlXHU2NWU1XHU2NzJjXHU2MGM1XHU1ODMxXHUzMGFhXHUzMGVhXHUzMGYzXHUzMGQ0XHUzMGMzXHUzMGFmIChKT0kpIFx1MzA5Mlx1NWJhM1x1NGYxZFx1MzA1OVx1MzA4Ylx1MzA1Zlx1MzA4MVx1MzA2Ylx1ZmYwYyBKT0kgXHUzMDZlXHUzMGVkXHUzMGI0XHUzMDkyXHUzMGUyXHUzMGMxXHUzMGZjXHUzMGQ1XHUzMDZiXHUzMDU3XHUzMDVmXHU2NWQ3XHUzMDkyXHU0ZjVjXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDZiXHUzMDZhXHUzMDYzXHUzMDVmXHVmZjBlIFx1NjVkN1x1MzA2Zlx1MzAwY1x1ODI2Zlx1MzA0NFx1NjVkN1x1MzAwZFx1MzA2N1x1MzA2YVx1MzA1MVx1MzA4Y1x1MzA3MFx1MzA2YVx1MzA4OVx1MzA2YVx1MzA0NFx1ZmYwZSBcdTMwMGNcdTgyNmZcdTMwNDRcdTY1ZDdcdTMwMGRcdTMwNjhcdTMwNmZcdWZmMGNcdTMwYTJcdTMwZWJcdTMwZDVcdTMwYTFcdTMwZDlcdTMwYzNcdTMwYzhcdTMwNmUgSiwgTywgSSBcdTMwNmVcdTMwNDRcdTMwNWFcdTMwOGNcdTMwNGJcdTMwNmVcdTY1ODdcdTViNTdcdTMwOTJcdWZmMGNcdTdlMjYgTSBcdTg4NGNcdWZmMGNcdTZhMmEgTiBcdTUyMTdcdTMwNmVcdTk1NzdcdTY1YjlcdTVmNjJcdTcyYjZcdTMwNmJcdTRlMjZcdTMwNzlcdTMwNWZcdTMwODJcdTMwNmVcdTMwNjdcdWZmMGMgSiwgTywgSSBcdTMwNGNcdTRlZTVcdTRlMGJcdTMwNmVcdTU2ZjNcdTMwNmVcdTMwODhcdTMwNDZcdTMwNmIgKFx1MzA1OVx1MzA2YVx1MzA4Zlx1MzA2MVx1ZmYwY0ogXHUzMDZlXHU1M2YzXHU5NmEzXHUzMDZiIE8gXHUzMDRjXHVmZjBjXHUzMDVkXHUzMDZlIEogXHUzMDZlXHU0ZTBiXHU5NmEzXHUzMDZiIEkgXHUzMDRjKSBcdTRlMjZcdTMwOTNcdTMwNjdcdTMwNDRcdTMwOGJcdTdiODdcdTYyNDBcdTMwNGNcdTY1ZDdcdTMwNmVcdTVjMTFcdTMwNmFcdTMwNGZcdTMwNjhcdTMwODIgMSBcdTMwNGJcdTYyNDBcdTMwNmJcdTMwNDJcdTMwOGJcdTMwODJcdTMwNmVcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9qb2kxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEwMHB4OyB3aWR0aDoxMDBweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdTRlZTVcdTRlMGJcdTMwNmVcdTU2ZjNcdTMwNmJcdWZmMGNcdTMwMGNcdTgyNmZcdTMwNDRcdTY1ZDdcdTMwMGRcdTMwNmVcdTRmOGJcdTMwOTIgMiBcdTMwNjRcdTc5M2FcdTMwNTlcdWZmMGU8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9qb2kyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE0OHB4OyB3aWR0aDozNDBweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdTRlZTVcdTRlMGJcdTMwNmVcdTU2ZjNcdTMwNmJcdWZmMGNcdTMwMGNcdTgyNmZcdTMwNDRcdTY1ZDdcdTMwMGRcdTMwNjdcdTMwNmZcdTMwNmFcdTMwNDRcdTRmOGJcdTMwOTIgMiBcdTMwNjRcdTc5M2FcdTMwNTlcdWZmMGU8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9qb2kzLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE0OHB4OyBvcGFjaXR5OjAuOTsgd2lkdGg6MzQwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHUzMDQ0XHUzMDdlIE0sIE4gXHUzMDZlXHU1MDI0XHVmZjBjXHUzMDRhXHUzMDg4XHUzMDczXHU2NWQ3XHUzMDZlXHU0ZTAwXHU5MGU4XHUzMDZlXHU1ODM0XHU2MjQwXHUzMDZiXHUzMDY0XHUzMDQ0XHUzMDY2IEosIE8sIEkgXHUzMDZlXHUzMDY5XHUzMDZlXHU2NTg3XHU1YjU3XHUzMDZiXHUzMDU5XHUzMDhiXHUzMDRiXHUzMDRjXHU2YzdhXHUzMDdlXHUzMDYzXHUzMDY2XHUzMDRhXHUzMDhhXHVmZjBjXHU1MTY1XHU1MjliXHUzMDY4XHUzMDU3XHUzMDY2XHUzMDVkXHUzMDZlXHU2MGM1XHU1ODMxXHUzMDRjXHU0ZTBlXHUzMDQ4XHUzMDg5XHUzMDhjXHUzMDhiXHVmZjBlIFx1ODAwM1x1MzA0OFx1MzA4OVx1MzA4Y1x1MzA4Ylx1MzAwY1x1ODI2Zlx1MzA0NFx1NjVkN1x1MzAwZFx1MzA2Zlx1NGY1NVx1OTAxYVx1MzA4YVx1MzA0Mlx1MzA4Ylx1MzA0Ylx1MzA5Mlx1OGEwOFx1N2I5N1x1MzA1N1x1ZmYwY1x1MzA1ZFx1MzA2ZVx1NjU3MFx1MzA5MiAxMDAwMDAgKD0xMDxzdXA+NTxcL3N1cD4pIFx1MzA2N1x1NTI3Mlx1MzA2M1x1MzA1Zlx1NGY1OVx1MzA4YVx1MzA5Mlx1NTFmYVx1NTI5Ylx1MzA1OVx1MzA4Ylx1MzBkN1x1MzBlZFx1MzBiMFx1MzBlOVx1MzBlMFx1MzA5Mlx1NGY1Y1x1NjIxMFx1MzA1Ylx1MzA4OFx1ZmYwZTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHU1MTY1XHU1MjliXHUzMDZmIDEgKyBNIFx1ODg0Y1x1MzA0Ylx1MzA4OVx1MzA2YVx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD4xIFx1ODg0Y1x1NzZlZVx1MzA2Ylx1MzA2Zlx1NjVkN1x1MzA2ZVx1NTkyN1x1MzA0ZFx1MzA1NVx1MzA5Mlx1ODg2OFx1MzA1OSAyIFx1MzA2NFx1MzA2ZVx1NjU3NFx1NjU3MCBNLCBOICgyIFx1MjI2NiBNIFx1MjI2NiAyMCwgMiBcdTIyNjYgTiBcdTIyNjYgMjApIFx1MzA0Y1x1N2E3YVx1NzY3ZFx1MzA2N1x1NTMzYVx1NTIwN1x1MzA4OVx1MzA4Y1x1MzA2Nlx1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD4xICsgaSBcdTg4NGNcdTc2ZWUgKDEgXHUyMjY2IGkgXHUyMjY2IE0pIFx1MzA2Ylx1MzA2Zlx1ZmYwY04gXHU2NTg3XHU1YjU3XHUzMDRiXHUzMDg5XHUzMDZhXHUzMDhiXHU2NTg3XHU1YjU3XHU1MjE3XHUzMDRjXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlIFx1NTQwNFx1NjU4N1x1NWI1N1x1MzA2ZiBKLCBPLCBJLCA/IFx1MzA2ZVx1MzA0NFx1MzA1YVx1MzA4Y1x1MzA0Ylx1MzA2N1x1MzA0Mlx1MzA4YVx1ZmYwYyBqIFx1NjU4N1x1NWI1N1x1NzZlZSAoMSBcdTIyNjYgaiBcdTIyNjYgTikgXHUzMDRjIEosIE8sIEkgXHUzMDZlXHUzMDQ0XHUzMDVhXHUzMDhjXHUzMDRiXHUzMDY3XHUzMDQyXHUzMDhiXHU1ODM0XHU1NDA4XHUzMDZmIGkgXHU4ODRjIGogXHU1MjE3XHUzMDZlXHU1ODM0XHU2MjQwXHUzMDZlXHU2NTg3XHU1YjU3XHUzMDRjXHUzMDVkXHUzMDhjXHUzMDVlXHUzMDhjIEosIE8sIEkgXHUzMDZiXHU2YzdhXHUzMDdlXHUzMDYzXHUzMDY2XHUzMDQ0XHUzMDhiXHUzMDUzXHUzMDY4XHVmZjBjID8gXHUzMDY3XHUzMDQyXHUzMDhiXHU1ODM0XHU1NDA4XHUzMDZmXHUzMDdlXHUzMDYwXHU2YzdhXHUzMDdlXHUzMDYzXHUzMDY2XHUzMDQ0XHUzMDZhXHUzMDQ0XHUzMDUzXHUzMDY4XHUzMDkyXHU4ODY4XHUzMDU5XHVmZjBlPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHU4MDAzXHUzMDQ4XHUzMDg5XHUzMDhjXHUzMDhiXHUzMDBjXHU4MjZmXHUzMDQ0XHU2NWQ3XHUzMDBkXHUzMDZlXHU1MDBiXHU2NTcwXHUzMDkyIDEwMDAwMCAoPTEwPHN1cD41PFwvc3VwPikgXHUzMDY3XHU1MjcyXHUzMDYzXHUzMDVmXHU0ZjU5XHUzMDhhXHUzMDkyIDEgXHU4ODRjXHUzMDY3XHU1MWZhXHU1MjliXHUzMDViXHUzMDg4XHVmZjBlPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2pvaTQucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjQ0cHg7IG9wYWNpdHk6MC45OyB3aWR0aDozNDBweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNzdjXHViY2Y4XHVjNWI0In1d