문제
성빈이는 새로 이사를 가면서 자신의 방에 가구를 배치했다. 그러나 성빈이는 아직 침대를 배치하지 않았다. 성빈이는 침대를 어떻게 배치할지 견적을 보고 있다.
성빈이의 방은 가로 M, 세로 N 크기의 격자 모양으로 이루어졌으며 침대는 1 × D 크기이다. 침대는 90도 돌려서 배치할 수 있으며, 30도, 60도 등의 다른 각도로는 돌릴 수 없다. 또, 침대는 정확히 격자에 맞게 배치해야 하고 다른 가구나 벽이 있는 곳에는 침대를 놓을 수 없다. 아래 사진은 성빈이가 방에 침대를 배치할 수 있는 모든 경우를 나타낸다.
성빈이를 도와 방의 정보가 주어지면 침대를 놓는 방법의 수를 구하는 프로그램을 작성하여라.
입력
첫 번째 줄에는 방의 크기 N, M과 침대의 길이 D가 주어진다. (1 ≦ N, M ≦ 100, 2 ≦ D ≦ 100)
두 번째 줄부터 N개의 줄에는 방의 정보가 주어진다. '.'는 빈 영역, '#'는 벽 혹은 가구가 놓인 곳을 의미한다.
출력
침대를 놓는 방법의 수를 출력한다.
예제1
입력
352
...#.
#...#
....#
출력
12
예제2
입력
475
.#.....
.....##
.......
#......
출력
7
출처
JOI 2017 예선