문제
한국 정보 올림피아드(KOI)에서는 올해 전국 대회를 홍보하기 위해 KOI 로고를 모티브로 한 깃발을 만들게했다.
깃발은 "좋은 깃발"이어야한다.
"좋은 깃발"은 알파벳 K, O, I 문자를 세로 M 행 옆 N 열의 직사각형 모양의 표에 배열 한 것으로,
K, O, I가 아래 그림과 같이 ( 즉 K의 오른쪽 옆에 O가 있고 K 아래에 I가 있는) 놓여있는 곳이 깃발에 적어도 1 개 이상 있는 것이다.
다음 그림은 "좋은 깃발"의 두 가지 예를 보이고 있다.
다음 그림은 "좋은 깃발"이 아닌 두 가지 예를 보이고 있다.
깃발의 가로 세로 크기와 깃발에 입력된 정보를 입력받아 “좋은 깃발”이 몇 가지가 만들어 질 수 있는지 구하는 프로그램을 작성하시오. 입력 예 1에 대해서는 아래 4가지 경우를 만들 수 있다.
입력
입력은 1 + M 행으로 구성된다. 첫 번째 줄에는 깃발의 크기를 나타내는 두 정수 M, N (2 <= M, N <= 20)가 공백으로 구분되어 적혀있다.
이 후 M행에는 N 개의 문자로 구성된 문자열이 적혀있다. 각 문자는 K, O, I, ? 중 하나이며, ? 이면 아직 정해지지 않았음을 나타낸다.
출력
입력된 정보를 바탕으로 만들 수 있는 좋은 깃발의 경우의 수를 100000으로 나눈 나머지를 구하시오.
예제1
입력
23
??O
IIK
출력
4
예제2
입력
22
??
??
출력
3
예제3
입력
33
??I
???
O?K
출력
53
예제4
입력
54
KOI?
????
????
????
?KOI
출력
28218
힌트
출처
joi 2010/2011 예선 6