0558 - JOI 旗 (JOI Flag)

問題

情報オリンピック日本委員会では，今年の日本情報オリンピック (JOI) を宣伝するために， JOI のロゴをモチーフにした旗を作ることになった． 旗は「良い旗」でなければならない． 「良い旗」とは，アルファベットの J, O, I のいずれかの文字を，縦 M 行，横 N 列の長方形状に並べたもので， J, O, I が以下の図のように (すなわち，J の右隣に O が，その J の下隣に I が) 並んでいる箇所が旗の少なくとも 1 か所にあるものである．

以下の図に，「良い旗」の例を 2 つ示す．

以下の図に，「良い旗」ではない例を 2 つ示す．

いま M, N の値，および旗の一部の場所について J, O, I のどの文字にするかが決まっており，入力としてその情報が与えられる． 考えられる「良い旗」は何通りあるかを計算し，その数を 100000 (=10⁵) で割った余りを出力するプログラムを作成せよ．

入力

入力は 1 + M 行からなる．

1 行目には旗の大きさを表す 2 つの整数 M, N (2 ≦ M ≦ 20, 2 ≦ N ≦ 20) が空白で区切られて書かれている．

1 + i 行目 (1 ≦ i ≦ M) には，N 文字からなる文字列が書かれている． 各文字は J, O, I, ? のいずれかであり， j 文字目 (1 ≦ j ≦ N) が J, O, I のいずれかである場合は i 行 j 列の場所の文字がそれぞれ J, O, I に決まっていること， ? である場合はまだ決まっていないことを表す．

出力

考えられる「良い旗」の個数を 100000 (=10⁵) で割った余りを 1 行で出力せよ．

入出力例

2 3
??O
IIJ

2 2
??
??

3 3
??I
???
O?J

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

4

3

53

28218

入力例 1 においては，以下の図の 4 通りの「良い旗」が考えられる．

入力例 4 においては，「良い旗」は 2428218 通り考えられるので，それを 100000 (=10⁵) で割った余りである 28218 を出力する．