Một cuộc thi lập trình quốc tế sắp được tổ chức tại Nhật Bản và địa điểm thi đang được chuẩn bị. Địa điểm được chia thành một lưới gồm \(N\) ô theo hướng Bắc - Nam và \(M\) ô theo hướng Đông - Tây. Một số ô đang chứa thiết bị phục vụ cuộc thi.

Để thí sinh nghỉ ngơi trong thời gian thi, ban tổ chức sẽ bố trí đồ ăn nhẹ và thức uống tại đúng một khu vực nghỉ giải lao. Khu vực nghỉ phải gồm \(D\) ô liên tiếp theo hướng Bắc - Nam hoặc theo hướng Đông - Tây. Không được bố trí khu vực nghỉ trên ô có thiết bị.

Hãy tính số cách bố trí khu vực nghỉ giải lao trong địa điểm thi.

Dữ liệu vào

Dữ liệu vào gồm \(N+1\) dòng:

• Dòng thứ nhất chứa ba số nguyên \(N, M, D\). Địa điểm có \(N\) ô theo hướng Bắc - Nam, \(M\) ô theo hướng Đông - Tây, và khu vực nghỉ gồm \(D\) ô liên tiếp theo một trong hai hướng đó.
• Mỗi dòng trong \(N\) dòng tiếp theo chứa một xâu gồm \(M\) ký tự mô tả địa điểm. Ký tự thứ \(j\) của dòng thứ \(i\) mô tả ô ở hàng thứ \(i\) tính từ phía Bắc và cột thứ \(j\) tính từ phía Tây. Ký tự # nghĩa là ô có thiết bị, còn . nghĩa là ô không có thiết bị.

Dữ liệu ra

In ra một số nguyên trên một dòng: số cách bố trí khu vực nghỉ giải lao.

Ràng buộc

Các giá trị thỏa mãn:

• \(1 \le N \le 100\).
• \(1 \le M \le 100\).
• \(2 \le D \le 100\).

Phân nhóm

Bài có năm bộ dữ liệu chấm, mỗi bộ trị giá \(20\) điểm.

Ví dụ

3 5 2
...#.
#...#
....#

12

4 7 5
.#.....
.....##
.......
#......

7

Nguồn

Kỳ thi chọn đội tuyển Olympic Tin học Nhật Bản JOI 2016/2017, vòng sơ khảo, bài 3: Refreshment Area.