시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 96 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+XHVjNzdjXHViZDgwIFx1YzcwNFx1Y2U1OFx1YzVkMFx1YjI5NCBcdWM3NzRcdWJiZjggXHVhZGY4IFx1Y2U3OFx1Yzc0NCBcdWNjNDRcdWM2YjggXHViYjM4XHVjNzkwXHVhYzAwIFx1YzgxNVx1ZDU3NFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIE0sIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjODhiXHVjNzQwIFx1YWU0M1x1YmMxY1x1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFlNDNcdWJjMWNcdWM3NTggXHVkMDZjXHVhZTMwIE1cdWFjZmMgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgTSwgTiAmbGU7IDIwKTxcL3A+XHJcblxyXG5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBNXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFlNDNcdWJjMWNcdWM3NTggXHViYWE4XHVjNTkxXHVjNzc4IE5cdWFjMWMgXHViYjM4XHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YmIzOFx1Yzc5MFx1YjI5NCBKLCBPLCBJLCA/XHVjOTExIFx1ZDU1OFx1YjA5OFx1Yzc3NFx1YjJlNC4gSiwgTywgSVx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgaVx1ZDU4OSBqXHVjNWY0IFx1YzcwNFx1Y2U1OFx1Yzc1OCBcdWJiMzhcdWM3OTBcdWFjMDAgXHVjNzc0XHViYmY4IFx1YWRmOCBcdWJiMzhcdWM3OTBcdWI4NWMgXHVjODE1XHVkNTc0XHVjODM4IFx1Yzc4OFx1YjI5NCBcdWI3M2JcdWM3NzRcdWFjZTAsID9cdWIyOTQgXHVjNTQ0XHVjOWMxIFx1YzgxNVx1ZDU3NFx1YzgzOCBcdWM3ODhcdWM5YzAgXHVjNTRhXHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwICZxdW90O1x1Yzg4Ylx1Yzc0MCBcdWFlNDNcdWJjMWMmcXVvdDtcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyAxMDAwMDBcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvam9pNC5wbmdcIiBzdHlsZT1cImhlaWdodDoyNDRweDsgd2lkdGg6MzQwcHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjU1NTkiLCJwcm9ibGVtX2xhbmciOiIyIiwidGl0bGUiOiJKT0kgXHU2NWQ3IChKT0kgRmxhZykiLCJkZXNjcmlwdGlvbiI6IjxwPlx1MzBhYVx1MzBlYVx1MzBmM1x1MzBkNFx1MzBjM1x1MzBhZlx1NjVlNVx1NjcyY1x1NTlkNFx1NTRlMVx1NGYxYVx1MzA2N1x1MzA2Zlx1ZmYwY1x1NGVjYVx1NWU3NFx1MzA2ZVx1NjVlNVx1NjcyY1x1NjBjNVx1NTgzMVx1MzBhYVx1MzBlYVx1MzBmM1x1MzBkNFx1MzBjM1x1MzBhZiAoSk9JKSBcdTMwOTJcdTViYTNcdTRmMWRcdTMwNTlcdTMwOGJcdTMwNWZcdTMwODFcdTMwNmJcdWZmMGMgSk9JIFx1MzA2ZVx1MzBlZFx1MzBiNFx1MzA5Mlx1MzBlMlx1MzBjMVx1MzBmY1x1MzBkNVx1MzA2Ylx1MzA1N1x1MzA1Zlx1NjVkN1x1MzA5Mlx1NGY1Y1x1MzA4Ylx1MzA1M1x1MzA2OFx1MzA2Ylx1MzA2YVx1MzA2M1x1MzA1Zlx1ZmYwZSBcdTY1ZDdcdTMwNmZcdTMwMGNcdTgyNmZcdTMwNDRcdTY1ZDdcdTMwMGRcdTMwNjdcdTMwNmFcdTMwNTFcdTMwOGNcdTMwNzBcdTMwNmFcdTMwODlcdTMwNmFcdTMwNDRcdWZmMGUgXHUzMDBjXHU4MjZmXHUzMDQ0XHU2NWQ3XHUzMDBkXHUzMDY4XHUzMDZmXHVmZjBjXHUzMGEyXHUzMGViXHUzMGQ1XHUzMGExXHUzMGQ5XHUzMGMzXHUzMGM4XHUzMDZlIEosIE8sIEkgXHUzMDZlXHUzMDQ0XHUzMDVhXHUzMDhjXHUzMDRiXHUzMDZlXHU2NTg3XHU1YjU3XHUzMDkyXHVmZjBjXHU3ZTI2IE0gXHU4ODRjXHVmZjBjXHU2YTJhIE4gXHU1MjE3XHUzMDZlXHU5NTc3XHU2NWI5XHU1ZjYyXHU3MmI2XHUzMDZiXHU0ZTI2XHUzMDc5XHUzMDVmXHUzMDgyXHUzMDZlXHUzMDY3XHVmZjBjIEosIE8sIEkgXHUzMDRjXHU0ZWU1XHU0ZTBiXHUzMDZlXHU1NmYzXHUzMDZlXHUzMDg4XHUzMDQ2XHUzMDZiIChcdTMwNTlcdTMwNmFcdTMwOGZcdTMwNjFcdWZmMGNKIFx1MzA2ZVx1NTNmM1x1OTZhM1x1MzA2YiBPIFx1MzA0Y1x1ZmYwY1x1MzA1ZFx1MzA2ZSBKIFx1MzA2ZVx1NGUwYlx1OTZhM1x1MzA2YiBJIFx1MzA0YykgXHU0ZTI2XHUzMDkzXHUzMDY3XHUzMDQ0XHUzMDhiXHU3Yjg3XHU2MjQwXHUzMDRjXHU2NWQ3XHUzMDZlXHU1YzExXHUzMDZhXHUzMDRmXHUzMDY4XHUzMDgyIDEgXHUzMDRiXHU2MjQwXHUzMDZiXHUzMDQyXHUzMDhiXHUzMDgyXHUzMDZlXHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvam9pMS5wbmdcIiBzdHlsZT1cImhlaWdodDoxMDBweDsgd2lkdGg6MTAwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHU0ZWU1XHU0ZTBiXHUzMDZlXHU1NmYzXHUzMDZiXHVmZjBjXHUzMDBjXHU4MjZmXHUzMDQ0XHU2NWQ3XHUzMDBkXHUzMDZlXHU0ZjhiXHUzMDkyIDIgXHUzMDY0XHU3OTNhXHUzMDU5XHVmZjBlPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvam9pMi5wbmdcIiBzdHlsZT1cImhlaWdodDoxNDhweDsgd2lkdGg6MzQwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHU0ZWU1XHU0ZTBiXHUzMDZlXHU1NmYzXHUzMDZiXHVmZjBjXHUzMDBjXHU4MjZmXHUzMDQ0XHU2NWQ3XHUzMDBkXHUzMDY3XHUzMDZmXHUzMDZhXHUzMDQ0XHU0ZjhiXHUzMDkyIDIgXHUzMDY0XHU3OTNhXHUzMDU5XHVmZjBlPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvam9pMy5wbmdcIiBzdHlsZT1cImhlaWdodDoxNDhweDsgb3BhY2l0eTowLjk7IHdpZHRoOjM0MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1MzA0NFx1MzA3ZSBNLCBOIFx1MzA2ZVx1NTAyNFx1ZmYwY1x1MzA0YVx1MzA4OFx1MzA3M1x1NjVkN1x1MzA2ZVx1NGUwMFx1OTBlOFx1MzA2ZVx1NTgzNFx1NjI0MFx1MzA2Ylx1MzA2NFx1MzA0NFx1MzA2NiBKLCBPLCBJIFx1MzA2ZVx1MzA2OVx1MzA2ZVx1NjU4N1x1NWI1N1x1MzA2Ylx1MzA1OVx1MzA4Ylx1MzA0Ylx1MzA0Y1x1NmM3YVx1MzA3ZVx1MzA2M1x1MzA2Nlx1MzA0YVx1MzA4YVx1ZmYwY1x1NTE2NVx1NTI5Ylx1MzA2OFx1MzA1N1x1MzA2Nlx1MzA1ZFx1MzA2ZVx1NjBjNVx1NTgzMVx1MzA0Y1x1NGUwZVx1MzA0OFx1MzA4OVx1MzA4Y1x1MzA4Ylx1ZmYwZSBcdTgwMDNcdTMwNDhcdTMwODlcdTMwOGNcdTMwOGJcdTMwMGNcdTgyNmZcdTMwNDRcdTY1ZDdcdTMwMGRcdTMwNmZcdTRmNTVcdTkwMWFcdTMwOGFcdTMwNDJcdTMwOGJcdTMwNGJcdTMwOTJcdThhMDhcdTdiOTdcdTMwNTdcdWZmMGNcdTMwNWRcdTMwNmVcdTY1NzBcdTMwOTIgMTAwMDAwICg9MTA8c3VwPjU8XC9zdXA+KSBcdTMwNjdcdTUyNzJcdTMwNjNcdTMwNWZcdTRmNTlcdTMwOGFcdTMwOTJcdTUxZmFcdTUyOWJcdTMwNTlcdTMwOGJcdTMwZDdcdTMwZWRcdTMwYjBcdTMwZTlcdTMwZTBcdTMwOTJcdTRmNWNcdTYyMTBcdTMwNWJcdTMwODhcdWZmMGU8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1NTE2NVx1NTI5Ylx1MzA2ZiAxICsgTSBcdTg4NGNcdTMwNGJcdTMwODlcdTMwNmFcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+MSBcdTg4NGNcdTc2ZWVcdTMwNmJcdTMwNmZcdTY1ZDdcdTMwNmVcdTU5MjdcdTMwNGRcdTMwNTVcdTMwOTJcdTg4NjhcdTMwNTkgMiBcdTMwNjRcdTMwNmVcdTY1NzRcdTY1NzAgTSwgTiAoMiBcdTIyNjYgTSBcdTIyNjYgMjAsIDIgXHUyMjY2IE4gXHUyMjY2IDIwKSBcdTMwNGNcdTdhN2FcdTc2N2RcdTMwNjdcdTUzM2FcdTUyMDdcdTMwODlcdTMwOGNcdTMwNjZcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGU8XC9wPlxyXG5cclxuPHA+MSArIGkgXHU4ODRjXHU3NmVlICgxIFx1MjI2NiBpIFx1MjI2NiBNKSBcdTMwNmJcdTMwNmZcdWZmMGNOIFx1NjU4N1x1NWI1N1x1MzA0Ylx1MzA4OVx1MzA2YVx1MzA4Ylx1NjU4N1x1NWI1N1x1NTIxN1x1MzA0Y1x1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZSBcdTU0MDRcdTY1ODdcdTViNTdcdTMwNmYgSiwgTywgSSwgPyBcdTMwNmVcdTMwNDRcdTMwNWFcdTMwOGNcdTMwNGJcdTMwNjdcdTMwNDJcdTMwOGFcdWZmMGMgaiBcdTY1ODdcdTViNTdcdTc2ZWUgKDEgXHUyMjY2IGogXHUyMjY2IE4pIFx1MzA0YyBKLCBPLCBJIFx1MzA2ZVx1MzA0NFx1MzA1YVx1MzA4Y1x1MzA0Ylx1MzA2N1x1MzA0Mlx1MzA4Ylx1NTgzNFx1NTQwOFx1MzA2ZiBpIFx1ODg0YyBqIFx1NTIxN1x1MzA2ZVx1NTgzNFx1NjI0MFx1MzA2ZVx1NjU4N1x1NWI1N1x1MzA0Y1x1MzA1ZFx1MzA4Y1x1MzA1ZVx1MzA4YyBKLCBPLCBJIFx1MzA2Ylx1NmM3YVx1MzA3ZVx1MzA2M1x1MzA2Nlx1MzA0NFx1MzA4Ylx1MzA1M1x1MzA2OFx1ZmYwYyA/IFx1MzA2N1x1MzA0Mlx1MzA4Ylx1NTgzNFx1NTQwOFx1MzA2Zlx1MzA3ZVx1MzA2MFx1NmM3YVx1MzA3ZVx1MzA2M1x1MzA2Nlx1MzA0NFx1MzA2YVx1MzA0NFx1MzA1M1x1MzA2OFx1MzA5Mlx1ODg2OFx1MzA1OVx1ZmYwZTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1ODAwM1x1MzA0OFx1MzA4OVx1MzA4Y1x1MzA4Ylx1MzAwY1x1ODI2Zlx1MzA0NFx1NjVkN1x1MzAwZFx1MzA2ZVx1NTAwYlx1NjU3MFx1MzA5MiAxMDAwMDAgKD0xMDxzdXA+NTxcL3N1cD4pIFx1MzA2N1x1NTI3Mlx1MzA2M1x1MzA1Zlx1NGY1OVx1MzA4YVx1MzA5MiAxIFx1ODg0Y1x1MzA2N1x1NTFmYVx1NTI5Ylx1MzA1Ylx1MzA4OFx1ZmYwZTxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9qb2k0LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI0NHB4OyBvcGFjaXR5OjAuOTsgd2lkdGg6MzQwcHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1Yzc3Y1x1YmNmOFx1YzViNCJ9XQ==