0591 - 色塗り (Color Painting)

問題

H 行 W 列のマス目に分けられている紙がある. 紙のそれぞれのマスは, 青, 黄色, 橙色, 赤色のいずれかの色が塗られている.

あなたは友達の JOI くんにこの紙を見せたいが, JOI 君は芸術家であり, 紙のデザインに厳しい. 具体的には, 紙が次の条件を満たしていないと JOI 君は怒ってしまう.

• 辺を共有するマスは異なる色でなければならない.
• 1 ≤ i ≤ H - 1 について, i 行 W 列目のマスは i + 1 行 1 列目のマスと異なる色でなければならない.
• JOI 君は 2 行 K 列からなるある紙のデザインをとても嫌うため, それが紙の中に含まれていてはならない. ただし, その 2 行 K 列の紙のデザインを 90 度, 180 度, 270 度回転したものは含んでいてもかまわない.

下図にいくつかの例を示す.

図 (A) 条件を満たす紙の例である.

図 (B), (C) は条件を満たさない紙の例である. 図 (B) には, JOI 君が嫌うデザインが含まれている. 図 (C) では, 1 行 3 列目のマスと 2 行 1 列目のマスが同じ色になっている.

JOI 君の機嫌を損ねないためにも, あなたは紙のうち何マスかを塗り替えることで JOI くんが怒らないようにしたい. そうするためには, 最低紙を何マス塗り替える必要があるだろうか. また, 最低限のマス数でを塗り替えることで作れる, 条件に当てはまる紙は何通りあるだろうか. 通り数についてはとても多くなることがあるため, 10009 で割ったあまりを求めよ.

入力

入力は H + 3 行からなる.

1 行目には 3 つの整数 H, W, K ( 2 ≤ H, W ≤ 9, 1 ≤ K ≤ min(W, 3) ) が空白を区切りとして書かれている.

1 + i (1 ≤ i ≤ H) 行にはそれぞれ W 文字からなる文字列が書かれており, 紙に最初に塗られている色の情報を表す. H 行のうちの i 行目の j 文字目 (1 ≤ i ≤ H, 1 ≤ j ≤ W) は, 紙の i 行目 j 列目のマスの色を表す 'B', 'Y', 'O', 'R' のいずれかの文字である. 'B' は青, 'Y' は黄色, 'O' は橙色, 'R' は赤を表す.

H + 1 + i (1 ≤ i ≤ 2) 行にはそれぞれ K 文字からなる文字列が書かれており, JOI 君が嫌いな紙のデザインの情報を表す. 2 行のうちの i 行目の j 文字目 (1 ≤ i ≤ 2, 1 ≤ j ≤ K) は, 紙のデザインの i 行目 j 列目のマスの色を表す 'B', 'Y', 'O', 'R' のいずれかの文字である. 'B' は青, 'Y' は黄色, 'O' は橙色, 'R' は赤を表す.

出力

1 行に, 最低限変えなければならないマスの個数と, その変え方の通り数 を 10009 で割ったあまりを, 空白区切りで 1 行で出力せよ.

入出力例

3 3 2
RBO
YYO
ORB
RB
YO

4 4 2
RYOB
OOBO
YYYY
YRYR
YB
BY

6 6 1
YYYYYY
YYYYYY
YYYYYY
YYYYYY
YYYYYY
YYYYYY
Y
B

2 1

4 26

20 1283

入力例 1 の場合, 以下の紙のみが 2 箇所の塗替えで達成できる紙である.

入力例 3 では, 20 回の塗り替えで条件を満たす塗り方が 9,019,392 通りある. これを 10009 で割ったあまりを出力することに注意せよ.