Tranh thủ ngày chủ nhật An được nghỉ học, An tìm cách treo bức tranh của mình lên một bức tường hình chữ nhật được biểu diễn bằng mảng có ~n~ hàng và ~m~ cột. Một số ô đã có đinh cắm sẵn, được đánh dấu bằng ký tự #. Các ô còn lại là ô trống, ký hiệu ..

Bức tranh có dạng hình chữ nhật với kích thước tùy ý, và có thể treo tại bất kỳ vị trí nào trên tường miễn là nó che nhiều nhất 1 chiếc đinh.

Yêu cầu: Tính số cách đặt tranh khác nhau trên tường sao cho mỗi cách không che quá 1 đinh.

Dữ liệu vào

• Dòng 1: Hai số nguyên ~n~ và ~m~ (~1 \le n, m \le 500~) – kích thước bức tường.
• ~n~ dòng tiếp theo: mỗi dòng chứa ~m~ ký tự (# hoặc .) mô tả trạng thái từng ô trên tường.

Kết quả

• Một số nguyên duy nhất là tổng số cách đặt bức ảnh hợp lệ.

Ví dụ

Đầu vào:

3 3
...
...
..#

Đầu ra:

36

Giải thích: Mỗi vị trí treo ảnh đều hợp lệ vì nó che phủ nhiều nhất một chiếc đinh.

Đầu vào:

4 4
....
.#..
#...
#.#.

Đầu ra:

76

Giải thích: Bức tranh không thể được đặt theo cách mà nó bao phủ các vị trí ~(3, 1)~ và ~(4, 1)~ cùng một lúc.

Giới hạn

• Có ~34\%~ số điểm với ~n, m \le 10~.
• Có ~34\%~ số điểm với ~n, m \le 100~.
• Có ~32\%~ số điểm không có ràng buộc thêm.