Càng vào sâu, trọng lực càng biến đổi. Protoype và Lam2012 đối mặt với một cấu trúc dạng lưới \(N \times M\). Một số ô có hố đen. Họ cần đặt các thiết bị ổn định tại một số ô sao cho không có hai thiết bị nào nằm trên cùng một hàng, cùng một cột, hoặc cùng một đường chéo (như quân Hậu). Tuy nhiên, một số ô đã bị hố đen phá hủy hoàn toàn.

Yêu cầu: Tính số cách đặt \(K\) thiết bị này. Vì kết quả có thể rất lớn, hãy xuất ra kết quả mod \(10^9 + 7\).

Input

• Dòng đầu tiên chứa ba số nguyên \(N, M, K\) (\(1 \le N, M \le 12, 1 \le K \le \min(N, M)\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa một chuỗi \(M\) ký tự:
  • . : Ô trống có thể đặt thiết bị.
  • # : Ô bị hố đen phá hủy.

Output

• Một số nguyên duy nhất là số cách đặt thiết bị lấy dư cho \(10^9 + 7\).

Example

4 4 4
....
.#..
....
....

1