성빈이는 새로 이사를 가면서 자신의 방에 가구를 배치했다. 그러나 성빈이는 아직 침대를 배치하지 않았다. 성빈이는 침대를 어떻게 배치할지 견적을 보고 있다.

 

성빈이의 방은 가로 M, 세로 N 크기의 격자 모양으로 이루어졌으며 침대는 1 × D 크기이다. 침대는 90도 돌려서 배치할 수 있으며, 30도, 60도 등의 다른 각도로는 돌릴 수 없다. 또, 침대는 정확히 격자에 맞게 배치해야 하고 다른 가구나 벽이 있는 곳에는 침대를 놓을 수 없다. 아래 사진은 성빈이가 방에 침대를 배치할 수 있는 모든 경우를 나타낸다.

 

 

성빈이를 도와 방의 정보가 주어지면 침대를 놓는 방법의 수를 구하는 프로그램을 작성하여라.

첫 번째 줄에는 방의 크기 N, M과 침대의 길이 D가 주어진다. (1 ≦ N, M ≦ 100, 2 ≦ D ≦ 100) 두 번째 줄부터 N개의 줄에는 방의 정보가 주어진다. '.'는 빈 영역, '#'는 벽 혹은 가구가 놓인 곳을 의미한다.

침대를 놓는 방법의 수를 출력한다.

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

12

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

7