Trong ngày hội STEM của trường, câu lạc bộ Tin học tổ chức một cuộc thi lập trình điều khiển robot di chuyển trên sa bàn. Sa bàn là một mặt phẳng được chia thành lưới ô vuông kích thước \(M \times N\) (gồm \(M\) dòng và \(N\) cột). Trên sa bàn, mỗi ô vuông có thể là một khu vực di chuyển an toàn (kí hiệu là số 0) hoặc một khu vực có chướng ngại vật (kí hiệu là số 1).

Để kiểm tra độ linh hoạt của thuật toán định vị, ban tổ chức đưa ra một thử thách: robot phải thực hiện một "hành trình đơn" đi qua đúng \(K\) ô an toàn. Một hành trình hợp lệ được định nghĩa như sau:

• Xuất phát từ một ô an toàn bất kỳ trên sa bàn.
• Ở mỗi bước, robot chỉ được phép di chuyển sang một ô an toàn kề cạnh (chung một cạnh) với ô hiện tại.
• Robot tuyệt đối không được phép đi vào khu vực chướng ngại vật và không được phép lặp lại (đi lại vào) bất kỳ ô nào đã từng ghé thăm trước đó trong cùng một hành trình.
• Tổng số ô an toàn mà robot đặt chân đến (tính cả ô xuất phát) phải bằng chính xác \(K\).

Yêu cầu: Cho trước kích thước \(M\), \(N\), độ dài hành trình \(K\) và bản đồ sa bàn. Hãy tính tổng số lượng hành trình đơn hợp lệ khác nhau mà robot có thể thực hiện. Hai hành trình được coi là khác nhau nếu dãy tọa độ các ô mà robot lần lượt đi qua là khác nhau.

Input

• Dòng đầu tiên gồm ba số nguyên dương \(M\), \(N\), \(K\) (\(M, N \leq 10\)).
• \(M\) dòng tiếp theo, mỗi dòng gồm \(N\) số nguyên có giá trị 0 hoặc 1, biểu diễn bản đồ sa bàn (0 là ô trống, 1 là chướng ngại vật). Các số được ghi cách nhau bởi một khoảng trắng.

Output

• Dòng duy nhất chứa một số nguyên là tổng số lượng hành trình đơn hợp lệ độ dài \(K\) đếm được.

Example

2 2 3
0 0
0 1

2

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(K = 4\).
• Subtask \(2\) (\(20\%\) số điểm): \(K = 8\).
• Subtask \(3\) (\(60\%\) số điểm): \(K = 10\).