AT_joi2011yo_f.JOI 旗 (JOI Flag)

日本信息奥林匹克委员会为了宣传今年的日本信息奥林匹克（JOI），计划制作一种以 JOI 字母为主题的旗帜。这种旗帜需要设计成「好的旗帜」。所谓「好的旗帜」，是指由字母 J、O、I 组成的 $M$ 行 $N$ 列的矩形排列，并且至少有一个区域满足下图所示的排列：J 的右边是 O，而 J 的下面是 I。

以下展示了两个「好的旗帜」的示例：

反之，下图中的两个则不是「好的旗帜」：

现在，你需要根据已知的 $M$ 和 $N$ 值，以及部分确定为 J、O、I 的位置，来计算所有可能的「好的旗帜」的总数。请输出这些「好的旗帜」数量对 $100\,000\ (=\ 10^5)$ 取模的结果。

输入包括 $1 + M$ 行。

第 $1$ 行包含两个整数 $M$ 和 $N$ ($2 \leq M \leq 20$，$2 \leq N \leq 20$)，表示旗帜的行数和列数。

接下来的 $M$ 行，每行是一个长度为 $N$ 的字符串，其中每个字符可以是 J、O、I 或 ?。若某位置为 J、O 或 I，则表示此位置的字母已确定；若为 ?，则表示此位置的字母尚未确定。

输出一个整数，表示所有可能的「好的旗帜」数量对 $100\,000\ (=\ 10^5)$ 取模的结果。

样例解释 1

在样例1中，有以下四种「好的旗帜」的可能性：

样例解释 4

在样例4中，总共有 $2\,428\,218$ 种「好的旗帜」，所以需要输出它对 $100\,000\ (=\ 10^5)$ 取模后的结果 $28\,218$。

本翻译由 AI 自动生成