Cắt ảnh chứa ngôi sao

Cho một bức ảnh đen trắng dạng ma trận $n\times m$ gồm các ký tự '0' và '1'. Ký tự '1' tương ứng với một điểm ảnh màu trắng, ký tự '0' là điểm ảnh màu đen.

Một ngôi sao được xác định bởi một điểm ảnh trắng nằm ở tâm cùng với bốn điểm ảnh trắng kề cạnh với nó (trên, dưới, trái, phải) — tức là một hình chữ thập gồm 5 điểm ảnh đều màu trắng:

 1
111
 1

Ta muốn cắt ra một vùng hình chữ nhật từ bức ảnh sao cho vùng đó chứa không ít hơn $k$ ngôi sao. Các ngôi sao có thể giao nhau, có thể dùng chung các điểm ảnh trắng. Một ngôi sao được coi là nằm trong vùng chữ nhật nếu cả 5 điểm ảnh tạo nên nó đều nằm trong vùng đó.

Cạnh của vùng chữ nhật song song với cạnh của bức ảnh, và đường cắt đi thẳng theo ranh giới giữa các điểm ảnh. Một vùng chữ nhật được xác định bởi một dải hàng liên tiếp và một dải cột liên tiếp của bức ảnh.

Hãy đếm số cách cắt ra một vùng chữ nhật thỏa mãn điều kiện trên. Hai cách được coi là khác nhau nếu vùng chữ nhật được cắt khác nhau.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$ và $k$.
• $n$ dòng tiếp theo, mỗi dòng chứa $m$ ký tự '0' hoặc '1' mô tả bức ảnh.

Dữ liệu ra

• Một số nguyên duy nhất — số cách cắt vùng chữ nhật chứa ít nhất $k$ ngôi sao.

Ràng buộc

• $1\le n,m\le 500$
• $1\le k\le n·m$
• Kết quả có thể vượt quá phạm vi số nguyên 32-bit.

Ví dụ