시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 2 1 1 50.000%

문제

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

「倉庫番」は 縦 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 盤面の横の長さ

예제 입력 1

3 5
..#..
.X...
##..#

예제 출력 1

9

解ける「倉庫番」の問題は以下に示す 9 通りが考えられる.

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

예제 입력 2

2 3
.X.
...

예제 출력 2

0

この例では,解ける「倉庫番」の問題を作ることができない.

예제 입력 3

4 7
.#.#.##
##.#..#
....X..
##.#...

예제 출력 3

24