问题

日本信息奥林匹克委员会决定制作一面以JOI标志为主题的旗帜来宣传今年的日本信息奥林匹克（JOI）。这面旗帜必须是一面“好旗帜”。所谓“好旗帜”，是指将拉丁字母J、O、I三个字母排列成$M$行$N$列的长方形，并且满足J、O、I在旗帜上至少有一个位置上按照以下图中所示的方式排列（即O在J的右边，I在J的下方）。

下图是两个示例“好旗帜”。

下图是两个示例不是“好旗帜”。

现在已经确定了$M$、$N$的值以及部分旗帜位置上应该是字母J、O、I中的哪个字母，并将这些信息作为输入给出。请编写一个程序计算可能的“好旗帜”的数量，并将该数量除以$100,000 (= 10^5)$所得的余数输出。

输入

输入由$1 + M$行组成。

第1行包含两个用空格分隔的整数$M$和$N$ $(2 \leqq M \leqq 20, 2 \leqq N \leqq 20)$，表示旗帜的大小。

第$1+i$行 $(1 \leqq i \leqq M)$包含一个由$N$个字符组成的字符串。每个字符可以是J、O、I或?。如果第$j$个字符$(1 \leqq j \leqq N)$是J、O或I，则表示第$i$行第$j$列的位置上的字符已经确定为相应的J、O或I；如果是?，则表示该位置尚未确定。

输出

请将可能的“好旗帜”的数量除以$100,000 (= 10^5)$所得的余数以1行输出。

示例 1

2 3
??O
IIJ

输出示例 1

4

在示例1中，可以考虑到以下四种“好旗帜”。

示例 2

2 2
??
??

输出示例 2

3

示例 3

3 3
??I
???
O?J

输出示例 3

53

示例 4

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

输出示例 4

28218

对于示例4，有$2,428,218$种可能的“好旗帜”，所以输出$28,218$，即$2,428,218$除以$100,000 (= 10^5)$的余数。