Việt và Hàn là hai kiến trúc sư đang thiết kế quy hoạch cho một khu đô thị sinh thái. Khi biểu diễn trên mặt phẳng tọa độ Descartes, bản đồ khu đất có dạng một hình chữ nhật có cạnh song song với hai trục tọa độ, với hai góc đối diện là \((1, 1)\) và \((N, M)\). Để thu thập dữ liệu phục vụ cho việc thiết kế khu đô thị, Việt và Hàn đã khảo sát các điểm đất có tọa độ nguyên bên trong khu đất này (kể cả các điểm trên biên). Kết quả khảo sát mỗi điểm đất được ghi nhận thuộc một trong hai loại: \(1\) (đất nền cứng, đủ điều kiện chịu lực) hoặc \(0\) (đất ngập nước, lún yếu).

Không gian xanh luôn đóng vai trò vô cùng quan trọng cho đời sống của dân cư; bởi thế, Hàn lên kế hoạch thiết kế một công viên cây xanh rộng lớn. Khu đất được quy hoạch để xây công viên trong dự tính của Hàn có các đặc tính sau:

• Là một tam giác vuông cân không suy biến.
• Các đỉnh của tam giác có tọa độ nguyên.
• Các cạnh góc vuông của tam giác song song với một trong hai trục tọa độ.

Ngoài ra, để đảm bảo kết cấu an toàn mà vẫn giữ được cảnh quan tự nhiên, Việt đề xuất một tiêu chí cho khu đất xây công viên này như sau: Toàn bộ các điểm đất đã được khảo sát (điểm có tọa độ nguyên) trên đường biên của khu đất phải là đất nền cứng (loại \(1\)). Các điểm bên trong khu đất có thể thuộc loại bất kỳ.

Yêu cầu: Hãy giúp Việt và Hàn tính số lượng cách chọn ra một khu đất xây công viên với các tiêu chí như trên.

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N, M \le 2000\)).
• Dòng thứ \(i\) trong số \(N\) dòng tiếp theo chứa một xâu gồm \(M\) ký tự \(0\) hoặc \(1\). Ký tự thứ \(j\) (\(1 \le j \le M\)) của xâu thể hiện loại đất của điểm \((i, j)\).

Output

• In ra một số nguyên duy nhất là số cách chọn ra một khu đất để xây công viên thỏa mãn mọi tiêu chí của Việt và Hàn.

Example

3 3
111
101
111

4

Scoring

• Subtask \(1\) (\(40\) điểm): \(N, M \le 100\).
• Subtask \(2\) (\(30\) điểm): \(N, M \le 300\).
• Subtask \(3\) (\(30\) điểm): Không có ràng buộc nào thêm.