006 - JOI 旗 (JOI Flag)

時間制限 8 秒 / メモリ制限 64 MB / 得点 100 / x 0 /


TLE
8sec
MLE
64MB
得点
100

問題

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

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

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

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

入力

入力は 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 (=105) で割った余りを 1 行で出力せよ.

入出力例


入力例 1 入力例 2 入力例 3 入力例 4
2 3
??O
IIJ
2 2
??
??
3 3
??I
???
O?J
5 4
JOI?
????
????
????
?JOI
 
出力例 1 出力例 2 出力例 3 出力例 4
4
3
53
28218

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

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