JOI 깃발

어떤 위원회가 JOI 로고를 본떠 깃발을 디자인했다. 깃발은 $M \times N$ 격자이며, 각 칸에는 세 문자 J, O, I 중 하나가 정확히 하나씩 들어간다.

다음과 같은 L자 모양이 깃발 안에 적어도 한 번 나타나면 그 깃발을 좋은 깃발이라고 부른다. 어떤 칸이 J이고, 그 칸의 바로 오른쪽 칸이 O이며, J가 있는 칸의 바로 아래 칸이 I인 경우이다.

J O
I .

(. 칸에는 어떤 문자가 와도 상관없고, 표시된 세 칸만 중요하다.) 형식적으로, $1 \le i \le M-1$, $1 \le j \le N-1$인 행 $i$와 열 $j$가 존재하여 $i$행 $j$열이 J, $i$행 $j+1$열이 O, $i+1$행 $j$열이 I이면 좋은 깃발이다.

일부 칸은 이미 특정 문자로 정해져 있다. 나머지 칸은 아직 정해지지 않았으며 J, O, I 중 어느 것이든 될 수 있다. $M$, $N$과 정해진 칸들이 주어졌을 때, 아직 정해지지 않은 칸들을 채워 좋은 깃발을 만드는 방법의 수를 구하여라. 그 수를 $100000$으로 나눈 나머지를 출력한다.

첫째 줄에 깃발의 행 수와 열 수를 나타내는 두 정수 $M$과 $N$이 주어진다 ($2 \le M, N \le 20$).

다음 $M$개의 줄에는 각각 깃발의 한 행을 나타내는 $N$개의 문자가 주어진다. 각 문자는 J, O, I, ? 중 하나이다. 문자인 경우 그 칸이 이미 해당 문자로 정해져 있다는 뜻이고, ?는 아직 정해지지 않았다는 뜻이다.

좋은 깃발을 만드는 방법의 수를 $100000$으로 나눈 나머지를 한 줄에 출력한다.

L자 모양에서 제약을 받는 칸은 세 칸뿐이며, J의 대각선 방향($2 \times 2$ 블록의 오른쪽 아래) 칸에는 어떤 문자가 와도 된다. 깃발 어딘가에 이 배치가 한 번만 나타나도 좋은 깃발이 되므로, 좋은 깃발이 아닌 경우의 수를 세어 전체 경우의 수에서 빼는 방식이 더 쉬울 때가 많다.