“仓库番”是一个长久以来深受人们喜爱的益智游戏。

“仓库番”在被划分为 $M \times N$ 个格子的正方形棋盘上进行。棋盘上有箱子，目标是通过操作玩家将箱子移动到目标地点。在本题中，我们考虑箱子只有一个的情况。棋盘上的部分格子是墙壁，玩家、箱子和目标地点都位于非墙壁的格子上（玩家和箱子不会离开棋盘）。可以进行以下任一操作：

• 选择一个与玩家所在格子相邻的、非墙壁且没有箱子的格子，将玩家移动到该格子。
• 如果玩家所在的格子与箱子所在的格子相邻，且箱子所在格子的另一侧（与玩家相对的方向）存在一个非墙壁的格子，则可以将箱子推到那个格子，并将玩家移动到箱子原本所在的格子。

在此，两个格子相邻是指它们共享一条边。

以下是“仓库番”问题的一个例子。字符 # 表示墙壁，字符 @ 表示玩家，字符 O 表示箱子，字符 X 表示目标地点，字符 . 表示其他格子。

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

从该状态开始，可以通过以下操作将箱子移动到目标地点：

1. 将玩家向右移动。
2. 将玩家向下移动。
3. 将箱子和玩家向左移动。
4. 将箱子和玩家向左移动。

另一方面，从以下状态开始，无法将箱子移动到目标地点：

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

当给定棋盘上墙壁的位置和目标地点时，你想要知道有多少种配置玩家和箱子的方式，使得“仓库番”问题是可以解决的。在此，可解决的“仓库番”问题是指可以通过重复多次操作将箱子移动到目标地点的初始配置。此外，玩家和箱子必须分别放置在非墙壁且不是目标地点的格子上，且玩家和箱子必须放置在不同的格子上。

题目描述

给定棋盘的大小、墙壁的位置以及目标地点，编写一个程序，求出有多少种可解决的“仓库番”问题。

数据范围

$1 \le M \le 1000$ 棋盘的纵向长度 $1 \le N \le 1000$ 棋盘的横向长度

输入格式

从标准输入读取以下内容：

• 第 1 行包含两个整数 $M, N$，以空格分隔，分别表示棋盘的纵向和横向长度。
• 接下来的 $M$ 行表示棋盘信息。每行由 $N$ 个字符组成。每个字符为 #, X, . 中的任意一个，其中 # 表示墙壁，X 表示目标地点，. 表示其他格子（也是玩家和箱子初始位置的候选）。字符 X 恰好出现 1 次。

输出格式

将可解决的“仓库番”问题的数量作为整数输出到标准输出。

子任务

在评分数据中，对于 20% 的分数，满足 $M \le 50, N \le 50$。

样例

样例输入 1

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

样例输出 1

9

样例输入 2

2 3
.X.
...

样例输出 2

0

样例输入 3

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

样例输出 3

24