Hình chữ nhật con tổng K

Cho một bảng số nguyên gồm $R$ hàng và $C$ cột, và một số nguyên $K$. Hãy đếm số hình chữ nhật con (xác định bởi cặp hàng $t\le b$ và cặp cột $l\le r$) có tổng đúng bằng $K$.

Dữ liệu vào

• Dòng 1: ba số nguyên $R$, $C$ và $K$.
• $R$ dòng tiếp theo, mỗi dòng $C$ số nguyên (có thể âm).

Dữ liệu ra

In ra một số nguyên — số hình chữ nhật con có tổng bằng $K$.

Ràng buộc

• $1\le R,C\le 120$
• $-{10}^6\le a_{i,j}\le {10}^6$
• $-{10}^{14}\le K\le {10}^{14}$

Ví dụ

Ghi chú

Số đáp số có thể tới $\left(\genfrac{}{}{0ex}{}{R+1}{2}\right)\left(\genfrac{}{}{0ex}{}{C+1}{2}\right)\approx 5·{10}^7$, dùng kiểu 64-bit cho cả tổng tiền tố lẫn đáp số.