Xây nhà

Sau nhiều năm tham dự trại hè kiếm tiền thưởng, Sơn Tùng dành dụm được một số tiền đủ để mua đất làm nhà. Mảnh đất cậu ta mua được có dạng hình chữ nhật với $N$ mét chiều rộng và $M$ mét chiều dài. Để dễ hình dung, mảnh đất có thể được chia thành $N\times M$ ô ($N$ hàng, $M$ cột), mỗi ô có một độ cao nhất định. Nhà của Sơn Tùng có thể xây trên một ô hoặc một số ô liền nhau có dạng hình chữ nhật (các cạnh nằm dọc theo đường lưới) và có cùng độ cao.

Yêu cầu: Hãy giúp Sơn Tùng đếm số phương án có thể xây được ngôi nhà của mình trên mảnh đất đã mua được, tức là đếm số hình chữ nhật con của lưới mà mọi ô bên trong có cùng độ cao. Hai phương án khác nhau nếu tập ô được chọn khác nhau.

Dữ liệu vào

• Dòng đầu ghi hai số nguyên $N$ và $M$.
• $N$ dòng tiếp theo, mỗi dòng ghi $M$ số nguyên $a_{i,j}$ biểu thị độ cao của mỗi ô vuông trong mảnh đất.

Các số trên cùng một dòng cách nhau ít nhất một khoảng trắng.

Dữ liệu ra

Ghi một số nguyên là số phương án có thể xây nhà.

Ràng buộc

• $1\le N,M\le 1000$;
• $1\le a_{i,j}\le {10}^9$.

Ví dụ