AT_joi2011yo_f JOI 旗 (JOI Flag)

[problemUrl]: https://atcoder.jp/contests/joi2011yo/tasks/joi2011yo_f 情報オリンピック日本委員会では，今年の日本情報オリンピック (JOI) を宣伝するために，JOI のロゴをモチーフにした旗を作ることになった．旗は「良い旗」でなければならない．「良い旗」とは，アルファベットの J，O，I のいずれかの文字を，縦 $ M $ 行，横 $ N $ 列の長方形状に並べたもので，J，O，I が以下の図のように (すなわち，J の右隣に O が，その J の下隣に I が) 並んでいる箇所が旗の少なくとも $ 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 $ 行で出力せよ． - - - - - -

### Sample Explanation 1 入力例 $ 1 $ においては，以下の図の $ 4 $ 通りの「良い旗」が考えられる． !\[2011-yo-t6-fig04.png\](https://img.atcoder.jp/joi2011yo/2011-yo-t6-fig04.png) - - - - - - ### Sample Explanation 2 \- - - - - - ### Sample Explanation 3 \- - - - - - ### Sample Explanation 4 入力例 $ 4 $ においては，「良い旗」は $ 2\,428\,218 $ 通り考えられるので，それを $ 100\,000\ (=\ 10^5) $ で割った余りである $ 28\,218 $ を出力する．