17775번 - Sokoban 다국어

「倉庫番」は，長年人々に愛され続けてきているパズルである．

「倉庫番」は 縦 M × 横 N マスの正方形に区切られた盤面で行われる．盤面上に箱があり，プレイヤー を操作して箱を目標地点へ動かすことが目的である．この問題では，箱が 1 個である場合を考える．盤面 の一部のマスは壁であり，プレイヤー・箱・目標地点は壁でない 1 マスに位置している (プレイヤーや箱は 盤面から出ることはない)．以下のいずれかの操作が可能である．

• プレイヤーがいるマスに隣接しているマスのうち壁でなく箱がないマスを 1 つ選び，プレイヤーをそ のマスへ移動させる．
• プレイヤーがいるマスと箱があるマスが隣接していて，さらに，箱のマスに隣接していてプレイヤー と反対側にある壁でないマスが存在するとき，箱をそのマスに動かし，プレイヤーを箱があったマス に移動させる．

ここで，マスとマスが隣接しているとは，それらのマスが 1 辺を共有することである．

以下に，「倉庫番」の問題の例を示す．文字 # は壁，文字 @ はプレイヤー，文字 O は箱，文字 X は目標地 点，文字 . はその他のマス目を表している．

..#@.
.X.O.
##..#

この状態からは，以下の操作によって箱を目標地点へ動かすことができる．

1. プレイヤーを右に動かす．
2. プレイヤーを下に動かす．
3. 箱とプレイヤーを左に動かす．
4. 箱とプレイヤーを左に動かす．

一方，次の状態からは箱を目標地点へ動かすことはできない．

..#..
.X.O.
##.@#

あなたは，盤面の壁の位置と目標地点が決まっているとき，プレイヤーと箱を配置して，解ける「倉庫 番」の問題が何通りできるか知りたい．ここで，解ける「倉庫番」の問題とは，操作を何回か繰り返して箱 を目標地点へ移動させることができるような初期配置を指す．また，プレイヤーと箱はそれぞれ壁でなく 目標地点と異なるマスに配置しなければならず，プレイヤーと箱は異なるマスに配置しなければならない．

盤面の大きさおよび盤面の壁の位置と目標地点が与えられたとき，解ける「倉庫番」の問題が何通りで きるかを求めるプログラムを作成せよ．

標準入力から以下の入力を読み込め．

• 1 行目には整数 M, N が空白を区切りとして書かれており，それぞれ盤面の縦と横の長さを表す．
• 続く M 行は盤面の情報を表す．各行は N 文字からなる．各文字は #X. のいずれかであり，文字 # は壁，文字 X は目標地点，文字 . はその他のマス目 (プレイヤーや箱の初期位置の候補でもある) を 表している．文字 X はちょうど 1 回現れる．

標準出力に，解ける「倉庫番」の問題が何通りできるかを表す整数を 1 行で出力せよ．

• 1 ≤ M ≤ 1 000 盤面の縦の長さ
• 1 ≤ N ≤ 1 000 盤面の横の長さ