C - Column Dance
Benihuki
2
s
1024
MB
300
点
問題文
$H$ 行 $W$ 列のマス目があり、いくつかのマスに丸印が書かれています。
$i$ 行目 $j$ 列目のマスには文字列 $A_i$ の $j$ 文字目が o なら丸印が書かれていて、x なら何も書かれていません。
今、いくつかの列を選びそれらの列にある丸印を全て消して、残ったマス目が「どの行もちょうど $1$ つずつ丸印が書かれている」状態にしたいです。
このような条件を満たす列の選び方の通り数を出力して下さい。
制約
- $1\le H,W \le16$
- $A_i$ は
oまたはxからなる文字列 - $|A_i| = W$
- 入力はすべて整数
入力
入力は以下の形式で与えられます。
$H\ W$
$A_1$
$A_2$
$\vdots$
$A_H$
出力
条件を満たす列の選び方の通り数を出力してください。
入力例 1
4 4
oxxx
oxxx
xoxo
xoox
出力例 1
2
2 行 列目または3,4 行 列目を塗りつぶしたときに条件を満たします。（13:13 修正）
入力例 2
16 16
xxoxxxxxxxxxxxoo
ooxxxxxxxoxxoxxx
xxoxxxxxxoxxxxxo
xxxoxxxxoxoxxxox
xxxxxxxxxoxxxxxo
xxxxxxoxxxxxxxxx
xxoxxxxxxxxxxxoo
xxxxxxxxxoxxoxxo
ooxxxxxxxxxxoxxx
xxxxxxxxxxxxoxoo
xxxxxxxxxoxxxxxo
xxxxxxxxxxxxxxoo
xxxxxxxoxxxxxxoo
xxoxxxxxxxxxxxxo
xxxxxxxoxoxxxxxo
xxxxxoxxxxxxxxoo
出力例 2
48