题目描述

经典的推箱子是一个来自日本的古老游戏，目的是在训练你的逻辑思考能力。在一个狭小的仓库中，要求把木箱放到指定的位置，稍不小心就会出现箱子无法移动或者通道被堵住的情况，所以需要巧妙的利用有限的空间和通道，合理安排移动的次序和位置，才能顺利的 完成任务。

这个游戏有一个相对简单的版本，就是只有一个木箱，要将其推到一个确定的目标位置。

举个例子：

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

其中 . 表示没有障碍的格子，# 表示有障碍的格子，X 表示目标位置（注意这个格子是没有障碍的），O 是箱子（对于人来说箱子存在的格子是不能越过的），@是人的位置。注意上面这个情况是可以将箱子推到目标点去的，因为人只要向右一格，向下一格，然后推着箱子向左走两格，就完成了任务。

而下面这个例子是无解的：

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

现在我们的主人公想知道，对于一个给定的地图（与上面两个不同的是没有了箱子和人的初始位置） ，有多少种箱子和人的初始摆放方法（箱子的初始位置和人的初始位置和目标位置必须两两不同）能够使得箱子能被人成功地推到目标位置。

输入格式

第一行为两个正整数 $n,m$。表示整个地图有 $n$ 行 $m$ 列。

接下来是一个 $n$ 行 $m$ 列的地图，用 $n$ 个长为 $m$ 的字符串表示。

输出格式

一行，包含一个整数，为方案总数。

样例输入

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

样例输出

9

数据范围及约定

对于 $100\%$ 的数据，$1 \le n,m \le 10^3$。

题目来源

JOI2012