레이팅 미적용설명
情報オリンピック日本委員会では,今年の日本情報オリンピック (JOI) を宣伝するために,
JOI のロゴをモチーフにした旗を作ることになった.
旗は「良い旗」でなければならない.
「良い旗」とは,アルファベットの J, O, I のいずれかの文字を,縦 M 行,横 N 列の長方形状に並べたもので,
J, O, I が以下の図のように (すなわち,J の右隣に O が,その J の下隣に I が)
並んでいる箇所が旗の少なくとも 1 か所にあるものである.
以下の図に,「良い旗」の例を 2 つ示す.
以下の図に,「良い旗」ではない例を 2 つ示す.
いま M, N の値,および旗の一部の場所について J, O, I のどの文字にするかが決まっており,入力としてその情報が与えられる.
考えられる「良い旗」は何通りあるかを計算し,その数を 100000 (=10 5 ) で割った余りを出力するプログラムを作成せよ.
제약
입력 형식
入力は 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 5 ) で割った余りを 1 行で出力せよ.
예제 1
입력
2 3
??O
IIJ출력
4문제 정보