Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Cơm đang triển khai xây dựng một sân bóng mini trên một cánh đồng cỏ siêu rộng lớn. Cánh đồng này được chia thành n x m ô, mỗi ô chỉ trồng được 1 trong 2 loại cỏ : cỏ sẫm màu và cỏ nhạt màu. Cơm muốn sân mini của mình có kích thức 32 x 32 ô và các ô này bắt buộc phải xen kẽ cỏ sẫm, cỏ nhạt thành một lưới dạng caro, cụ thể hơn với ‘#’ là cỏ sẫm , ‘_’ là cỏ nhạt thì sân bóng của Cơm phải có dạng đúng như ma trận dưới đây.

_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#

#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_

_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#

#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_

_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#

#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_

_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#

#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_

_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#

#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_

_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#

#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_

_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#

#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_

_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#

#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_

_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#

#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_

_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#

#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_

_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#

#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_

_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#

#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_

_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#

#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_

_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#

#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_

_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#

#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_

_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#

#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_

Cho ma trận kích thước n x m mô tả đồng cỏ, yêu cầu đếm số lượng cách để đặt sân bóng trên đồng cỏ này.

Input

-          Dòng đầu là 2 số nguyên dương n và m là số hàng và số cột của ma trận cánh đồng (1 <= n , n <= 2000)

-          n dòng tiếp theo mỗi dòng m ký tự mô tả ma trận cánh đồng chỉ gồm các ký tự '#' và '_'

Output

-          số lượng cách lấy ra ô vuông 32 x 32 có dạng như sân bóng mà Cơm muốn xây dựng

Example

Input:
42 42
__________________________________________
__________________________________________
__________________________________________
__________________________________________
__________________________________________
______#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_____
_____#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#______
______#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_____
_____#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#______
______#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_____
_____#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#______
______#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_____
_____#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#______
______#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_____
_____#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#______
______#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_____
_____#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#______
______#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_____
_____#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#______
______#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_____
_____#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#______
______#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_____
_____#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#______
______#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_____
_____#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#______
______#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_____
_____#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#______
______#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_____
_____#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#______
______#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_____
_____#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#______
______#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_____
_____#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#______
______#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_____
_____#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#______
______#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_____
_____#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#______
__________________________________________
__________________________________________
__________________________________________
__________________________________________
__________________________________________

Output:
1