← 返回题目列表

AtCoder · joi2011yo_f

F. JOI 标志

中文机器翻译题面 查看原题

配点: 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 。