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 自动生成**