Problem Description

The Japan Olympiad in Informatics (JOI) Committee decided to create a flag inspired by the JOI logo to promote this year's JOI. The flag must be a "good flag." A "good flag" is a rectangular arrangement of letters J, O, and I in a grid of size \( M \) rows by \( N \) columns, where at least one occurrence of the sequence J, O, I appears as shown in the following diagram (i.e., O is to the right of J and I is below J).

The following diagrams show examples of "good flags."

The following diagrams show examples of flags that are not "good flags."

Given the values of \( M \) and \( N \), and some predetermined letters for certain positions on the flag, your task is to calculate the number of possible "good flags" and output the result modulo \( 100,000 \).

Input Format

The input consists of \( 1 + M \) lines.

The first line contains two integers \( M \) and \( N \) (\( 2 \leq M \leq 20 \), \( 2 \leq N \leq 20 \)) separated by a space, representing the size of the flag.

The \( 1 + i \)-th line (\( 1 \leq i \leq M \)) contains a string of \( N \) characters. Each character is either J, O, I, or ?, where J, O, I indicate the predetermined letter for the \( i \)-th row and \( j \)-th column, and ? indicates an undecided position.

Output Format

Output the number of possible "good flags" modulo \( 100,000 \) on a single line.

Sample Input and Output

Sample Input #1

2 3
??O
IIJ

Sample Output #1

4

Sample Input #2

2 2
??
??

Sample Output #2

3

Sample Input #3

3 3
??I
???
O?J

Sample Output #3

53

Sample Input #4

5 4
JOI?
????
????
????
?JOI

Sample Output #4

28218

Notes/Hints

Sample Explanation 1

For Sample Input #1, the following four "good flags" are possible.

Sample Explanation 2

Sample Explanation 3

Sample Explanation 4

For Sample Input #4, there are \( 2,428,218 \) possible "good flags", so the output is \( 28,218 \), which is the remainder when divided by \( 100,000 \).

见题面 Input 部分

见题面 Output 部分