joi 2010/2011 예선 6- KOI깃발 (KOI Flag) > 문제은행 : 정보올림피아드&알고리즘




2894 : KOI깃발 (KOI Flag)

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
1 회   
시도횟수
1 회   

문제

한국 정보 올림피아드(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으로 나눈 나머지를 구하시오.

입력 예

2 3
??O
IIK

출력 예

4

입력 예

2 2
??
??

출력 예

3

입력 예

3 3
??I
???
O?K

출력 예

53

입력 예

5 4
KOI?
????
????
????
?KOI

출력 예

28218

Hint!




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP