Bảng khóa

Công ty của Nam vừa cho ra mắt một loại ổ khóa mới có dạng một bảng hình chữ nhật kích thước h x w. Trên bảng có một số ô là phím bấm. Ổ khóa được mở bằng cách bấm đúng k phím phân biệt ở k ô khác nhau, đồng thời k ô này phải liên thông với nhau. Một tập hợp các ô được gọi là liên thông nếu từ một ô bất kỳ trong tập hợp đều có thể đi tới mọi ô còn lại thông qua một dãy các ô kề cạnh (chung cạnh) thuộc tập hợp đó.

Độ tin cậy của ổ khóa phụ thuộc vào số cách chọn ra k ô phím bấm liên thông. Hai cách chọn được coi là khác nhau nếu tồn tại ít nhất một ô thuộc cách chọn này nhưng không thuộc cách chọn kia.

Ổ khóa được mô tả bằng một lưới kích thước h x w, trong đó ô có phím bấm được ký hiệu bằng ký tự #, còn các ô khác được ký hiệu bằng ký tự ..

Yêu cầu: Cho ba số nguyên h, w, k và lưới mô tả các phím bấm, hãy đếm số cách chọn k ô phím bấm liên thông.

Đầu vào:

• Dòng đầu tiên gồm ba số nguyên h, w, k (1 <= h, w <= 30, 1 <= k <= 10).
• h dòng tiếp theo, mỗi dòng chứa một xâu ký tự độ dài w mô tả bảng khóa.

Đầu ra:

• In ra một số nguyên duy nhất là số tập hợp hợp lệ gồm k ô phím bấm liên thông.

Ví dụ 1:

Đầu vào:

5 6 7
.#....
##.##.
..#.#.
.####.
.....#

Đầu ra:

3

Ràng buộc:

• Subtask 1 (50% số điểm): k <= 3
• Subtask 2 (50% số điểm): k <= 10