"Sokoban" is a puzzle that has been loved by people for many years.

"Sokoban" is played on a board divided into an $M \times N$ grid. There is a box on the board, and the goal is to move the box to a target location by controlling a player. In this problem, we consider the case where there is only one box. Some cells on the board are walls, and the player, the box, and the target location are each located in a cell that is not a wall (the player and the box never leave the board). The following operations are possible:

• Choose a cell adjacent to the player's current cell that is not a wall and does not contain the box, and move the player to that cell.
• If the player's current cell is adjacent to the box's cell, and there exists a cell adjacent to the box's cell that is on the opposite side of the player and is not a wall, move the box to that cell and move the player to the cell where the box was.

Here, two cells are adjacent if they share one edge.

An example of a "Sokoban" problem is shown below. The character # represents a wall, @ represents the player, O represents the box, X represents the target location, and . represents other cells.

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

From this state, the box can be moved to the target location by the following operations:

1. Move the player to the right.
2. Move the player down.
3. Move the box and the player to the left.
4. Move the box and the player to the left.

On the other hand, from the following state, the box cannot be moved to the target location:

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

Given the positions of the walls and the target location on the board, you want to know how many ways you can place the player and the box to create a solvable "Sokoban" problem. Here, a solvable "Sokoban" problem refers to an initial configuration where the box can be moved to the target location by repeating the operations some number of times. Also, the player and the box must each be placed in a cell that is not a wall and is not the target location, and the player and the box must be placed in different cells.

Task

Create a program that, given the size of the board and the positions of the walls and the target location, calculates how many ways a solvable "Sokoban" problem can be created.

Constraints

$1 \le M \le 1000$ $1 \le N \le 1000$

Input

Read the following from standard input:

• The first line contains two integers $M$ and $N$ separated by a space, representing the height and width of the board, respectively.
• The following $M$ lines represent the board information. Each line consists of $N$ characters. Each character is one of #, X, or ., where # is a wall, X is the target location, and . is another cell (which is also a candidate for the initial position of the player or the box). The character X appears exactly once.

Output

Output the number of ways to create a solvable "Sokoban" problem as an integer on a single line.

Subtasks

For 20% of the points, $M \le 50$ and $N \le 50$.

Examples

Input 1

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

Output 1

9

Input 2

2 3
.X.
...

Output 2

0

Input 3

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

Output 3

24