Sokoban là một trò chơi giải đố được yêu thích từ lâu. Trò chơi diễn ra trên một bảng gồm \(M\) hàng và \(N\) cột ô vuông. Người chơi điều khiển một nhân vật để đẩy thùng đến ô đích. Trong bài này, chỉ có một chiếc thùng.

Một số ô trên bảng là tường. Nhân vật, thùng và đích đều nằm trên những ô không phải tường; nhân vật và thùng không bao giờ đi ra ngoài bảng. Có thể thực hiện một trong hai thao tác sau:

• Chọn một ô kề với ô của nhân vật, không phải tường và không có thùng, rồi di chuyển nhân vật đến ô đó.
• Nếu nhân vật đứng kề thùng, đồng thời ô ngay phía bên kia của thùng theo hướng đẩy nằm trong bảng và không phải tường, đẩy thùng đến ô đó và di chuyển nhân vật đến ô mà thùng vừa rời khỏi.

Hai ô được gọi là kề nhau nếu chúng có chung một cạnh.

Trong các hình minh họa, # là tường, @ là nhân vật, O là thùng, X là đích và . là các ô còn lại. Xét trạng thái sau:

Có thể đưa thùng đến đích bằng các thao tác:

1. Di chuyển nhân vật sang phải.
2. Di chuyển nhân vật xuống dưới.
3. Đẩy thùng và di chuyển nhân vật sang trái.
4. Đẩy thùng và di chuyển nhân vật sang trái một lần nữa.

Ngược lại, không thể đưa thùng đến đích từ trạng thái sau:

Khi vị trí các bức tường và ô đích đã cố định, bạn muốn biết có bao nhiêu cách đặt nhân vật và thùng để tạo thành một trò Sokoban có thể giải được. Một cách đặt có thể giải được nếu có thể thực hiện một dãy thao tác để đưa thùng đến đích.

Ban đầu, nhân vật và thùng phải nằm ở hai ô khác nhau; cả hai ô đều không phải tường và không phải ô đích.

Yêu cầu

Hãy đếm số cách đặt thỏa mãn yêu cầu.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn:

• Dòng đầu tiên chứa hai số nguyên \(M\) và \(N\), lần lượt là số hàng và số cột của bảng.
• \(M\) dòng tiếp theo mô tả bảng, mỗi dòng gồm \(N\) ký tự. Ký tự # biểu diễn tường, X biểu diễn đích và . biểu diễn các ô còn lại, cũng là những ô có thể chọn làm vị trí ban đầu của nhân vật hoặc thùng. Ký tự X xuất hiện đúng một lần.

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa số cách đặt nhân vật và thùng để tạo thành một trò Sokoban có thể giải được.

Ràng buộc

• \(1 \le M \le 1\,000\).
• \(1 \le N \le 1\,000\).
• Mỗi ký tự trên bảng là một trong ba ký tự #, X, ..
• Bảng có đúng một ký tự X.

Phân nhóm

• Các bộ kiểm thử chiếm \(20\%\) tổng số điểm thỏa mãn \(M \le 50\) và \(N \le 50\).

Ví dụ

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

9

2 3
.X.
...

0

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

24