Giải bài trực tuyến

John có một mảnh đất hình chữ nhật kích thước m x n. Anh quyết định đầu tư trồng hoa trên mảnh đất này nên đã quyết định chia nhỏ mảnh đất ra làm m x n khuôn, mỗi khuôn là một hình vuông bằng nhau để trồng các loại hoa khác nhau. Sau khi khảo sát đất, John thấy rằng một số khuôn đã bị nhiễm mặn, không thể trồng hoa được.

Do mới lần đầu tiên bắt tay vào kinh doanh nên John chỉ đủ vốn mua giống hoa để trồng trên k khuôn của mảnh đất. John muốn chọn ra k khuôn đất không bị nhiễm mặn để bắt đầu công việc, hơn nữa k khuôn này phải liên thông (kề cạnh) với nhau để thuận tiện cho việc chăm sóc tưới tiêu. John đang phân vân không biết chọn những khuôn đất nào cho phù hợp. Anh ta đã nhờ bạn tính xem có bao nhiêu cách chọn k khuôn đất thỏa mãn.

Input

Dòng đầu tiên chứa 3 số nguyên m, n, k (m, n ≤ 100; 1 ≤ k ≤ 6).

m dòng tiếp theo, mỗi dòng chứa n số nguyên a_ij với giá trị là 0 hoặc 1 tương đương với việc khuôn đất đó chưa bị nhiễm mặn và đã bị nhiễm mặn theo thứ tự.

Output

Đưa ra kết quả là số cách chọn k khuôn đất thỏa mãn yêu cầu của John.

Example

Input:
3 3 3
0 0 0
1 0 1
0 1 0
Output:
3