소코반

창고지기는 세로 $M$칸, 가로 $N$칸으로 나뉜 판에서 진행하는 퍼즐이다. 판 위에 상자가 하나 있고, 플레이어를 조작해 상자를 목표 지점으로 옮기는 것이 목표이다. 일부 칸은 벽이다. 플레이어, 상자, 목표 지점은 벽이 아닌 칸 하나씩에 놓여 있다. 플레이어와 상자는 판 밖으로 나갈 수 없다.

다음 두 가지 동작이 가능하다.

• 플레이어가 있는 칸과 인접한 칸 가운데 벽이 아니고 상자가 없는 칸을 하나 골라, 플레이어를 그 칸으로 옮긴다.
• 플레이어가 있는 칸과 상자가 있는 칸이 인접해 있고, 상자 칸에 인접한 칸 가운데 플레이어와 반대편에 있으며 벽이 아닌 칸이 있으면, 상자를 그 칸으로 옮기고 플레이어는 상자가 있던 칸으로 이동한다.

두 칸이 인접한다는 것은 변을 공유한다는 뜻이다.

다음은 예시이다. #은 벽, @은 플레이어, O는 상자, X는 목표 지점, .은 빈 칸이다.

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

이 상태에서는 다음 순서로 동작해 상자를 목표 지점으로 옮길 수 있다.

1. 플레이어를 오른쪽으로 움직인다.
2. 플레이어를 아래로 움직인다.
3. 상자와 플레이어를 왼쪽으로 움직인다.
4. 상자와 플레이어를 왼쪽으로 움직인다.

반면 다음 상태에서는 상자를 목표 지점으로 옮길 수 없다.

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

판의 벽 위치와 목표 지점이 정해져 있을 때, 플레이어와 상자를 배치해 풀 수 있는 창고지기 문제가 몇 가지나 되는지 구하라. 풀 수 있는 문제란 연속된 동작으로 상자를 목표 지점까지 옮길 수 있는 초기 배치를 말한다. 플레이어와 상자는 각각 벽이 아니고 목표 지점이 아닌 칸에 놓아야 하며, 서로 다른 칸에 놓아야 한다.

첫 번째 줄에 공백으로 구분된 정수 $M$, $N$이 주어진다. 각각 판의 세로와 가로 길이이다.

이어지는 $M$개의 줄은 판의 정보이다. 각 줄은 $N$개의 문자로 이루어진다. 각 문자는 #, X, . 중 하나이다. #은 벽, X는 목표 지점, .은 그 밖의 칸으로 플레이어나 상자의 초기 위치 후보이기도 하다. X는 정확히 한 번 나타난다.

풀 수 있는 창고지기 문제가 몇 가지인지 나타내는 정수를 한 줄에 출력한다.

• $1 \le M \le 1000$ (판의 세로 길이)
• $1 \le N \le 1000$ (판의 가로 길이)