문제
정보올림피아드 일본위원회는 올해 일본 정보올림피아드(JOI)를 알리려고 JOI 로고를 본뜬 깃발을 만들기로 했다. 깃발은 「좋은 깃발」이어야 한다. 「좋은 깃발」이란 알파벳 J, O, I 중 하나를 세로 \(M\)행, 가로 \(N\)열의 직사각형으로 늘어놓은 것으로, J의 오른쪽에 O가 있고 그 J의 아래에 I가 있는 곳이 깃발에 적어도 한 군데 있는 것을 말한다. 지금 \(M\), \(N\)의 값과, 깃발의 일부 칸에 대해 J, O, I 중 어떤 글자로 할지 이미 정해져 있으며, 그 정보가 입력으로 주어진다. 가능한 「좋은 깃발」이 몇 가지인지 세어, 그 수를 \(100000\)(\(=10^{5}\))으로 나눈 나머지를 출력하는 프로그램을 작성하라. |
입력
입력은 다음 형식으로 주어진다.
\(M\) \(N\)
\(S_1\)
\(S_2\)
\(\vdots\)
\(S_M\)
- 입력은 \(1+M\)줄이다.
- 첫째 줄에 깃발의 크기를 나타내는 정수 \(M\), \(N\)이 공백 하나로 구분되어 주어진다.
- \(1+i\)번째 줄(\(1 \le i \le M\))에 길이 \(N\)의 문자열이 공백 없이 주어진다.
- 각 문자는 J, O, I, ? 중 하나이다. \(j\)번째 문자(\(1 \le j \le N\))가 J, O, I이면 \(i\)행 \(j\)열의 글자가 그것으로 정해져 있고, ?이면 아직 정해지지 않았다.
- \(2 \le M \le 20\)
- \(2 \le N \le 20\)
출력
다음 형식으로 출력한다.
첫째 줄에 가능한 「좋은 깃발」의 개수를 \(100000\)(\(=10^{5}\))으로 나눈 나머지를 출력한다.
예시 1
입력
2 3
??O
IIJ
출력
4
예시 2
입력
2 2
??
??
출력
3
예시 3
입력
3 3
??I
???
O?J
출력
53
예시 4
입력
5 4
JOI?
????
????
????
?JOI
출력
28218
설명
「좋은 깃발」은 \(2428218\)가지이므로, 이를 \(100000\)으로 나눈 나머지 \(28218\)을 출력한다.