JOI Flag

A committee designed a flag based on the JOI logo. The flag is an $M \times N$ grid, and each cell holds exactly one of the three letters J, O, I.

A flag is called good if the following L-shaped arrangement appears at least once: some cell contains J, the cell immediately to its right contains O, and the cell immediately below the J contains I.

J O
I .

(The . cell may hold any letter; only the three marked cells matter.) Formally, the flag is good if there exist a row $i$ and a column $j$ with $1 \le i \le M-1$ and $1 \le j \le N-1$ such that the cell at row $i$, column $j$ is J, the cell at row $i$, column $j+1$ is O, and the cell at row $i+1$, column $j$ is I.

Some cells are already fixed to a specific letter. The remaining cells are still undecided and may become any of J, O, I. Given $M$, $N$, and which cells are fixed, count the number of ways to fill in the undecided cells so that the resulting flag is good. Print this count modulo $100000$.

The first line contains two integers $M$ and $N$ ($2 \le M, N \le 20$), the number of rows and columns of the flag.

Each of the next $M$ lines contains $N$ characters describing one row of the flag. Each character is J, O, I, or ?. A letter means the cell is already fixed to that letter; ? means the cell is still undecided.

Print a single integer: the number of good flags, modulo $100000$.

Only the three cells of the L shape are constrained; the cell diagonally opposite the J (the bottom-right of the $2 \times 2$ block) may hold any letter. A single occurrence anywhere in the flag is enough to make it good, so it is often easier to count the flags that are not good and subtract from the total number of fillings.