配点: 100 点
問題
日本信息奥林匹克委员会决定制作一面以JOI标志为主题的旗帜,以宣传今年的日本信息奥林匹克(JOI)。该旗帜必须是一面“好旗帜”。“好旗帜”是字母表中带有字母 J、O 或 I 的旗帜。 M 行,横 N J、O、I 如下图所示排列的矩形行(即 O 在 J 的右侧,I 在 J 的下方),并且标志至少位于 1 它是位于某处的东西。

下图显示了“好标志”的示例。 2 显示一个。

下图显示了一个不是“好标志”的示例。 2 显示一个。

现在 M, N 的值和用于标志某些部分的字符 J、O 或 I 被确定,并且该信息作为输入给出。计算有多少个可能的“好标志”,并计算该数量。 编写一个程序,输出除以 100\,000 \ (= 10^5) 后的余数。
入力
输入是 有一条 1 + M 行组成。
1 线代表旗帜的大小 2 整数 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 下图中, 4 可以考虑在街上挂“好旗子”。 在

入力例 2
2 2 ?? ??
出力例 2
3
入力例 3
3 3 ??I ??? O?J
出力例 3
53
入力例 4
5 4 JOI? ???? ???? ???? ?JOI
出力例 4
28218
入力例 4 中,“好标志”是 可以考虑 2\,428\,218 ,所以 输出 100\,000 \ (= 10^5) 所得的余数 28\,218 。