C - 菱型カウント

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

R 行、横 C 列の長方形領域がある。上から i (1 ≦ i ≦ R) 行目、左から j (1 ≦ j ≦ C) 列目にあるマスをマス (i, j) と呼ぶことにする。これらのマスのうちいくつかのマスは黒く、他のマスは白く塗られている。

また、ある整数 K が定められている。

ここで、以下の条件を満たすように新たに緑色を塗ることを考える。この操作は1 回だけ行う。

  • ある整数 の組 x (K ≦ x ≦ R - K + 1), y (K ≦ y ≦ C - K + 1) に対して、|i-x|+|j-y|≦ K - 1 を満たすすべてのマス (i,j) について、マス (i,j) は元々白いマスで、かつ、この操作で緑色に塗られる。さらに、|i-x|+|j-y|≧ K を満たすすべてのマスについて、そのマスは緑色に塗らない。

このような色の塗り方の総数はいくらか。ただし、ここでいう塗り方とは、どのマスがどの色になったかという組み合わせのことで、色の塗る順番は考慮しないものとする。


入力

入力は以下の形式で標準入力から与えられる。

R C K
s_1
s_2
:
s_R
  • 1 行目には、3 つの整数 R (3 ≦ R ≦ 500), C (3 ≦ C ≦ 500), K (2 ≦ K ≦ 500) が空白区切りで書かれている。これは、長方形領域が縦 R 行、横 C 列あることを表す。K は文中で定められた整数である。
  • 2 行目から R 行には、マスに関する情報が与えられる。R 行のうち i (1 ≦ i ≦ R) 行目には、長さ C の文字列 s_i が与えられる。文字列 s_io, x2 種類の文字でのみ構成されており、s_i の左から j (1 ≦ j ≦ C) 文字目の文字が o ならマス (i,j) が白いマスであることを、x ならマス (i,j) が黒いマスであることを表す。

部分点

この問題には部分点が設定されている。

  • R ≦ 50 かつ C ≦ 50 を満たすデータセット 1 に正解した場合は、30 点が与えられる。

出力

緑色の塗り方の総数を 1 行に出力せよ。出力の末尾に改行を入れること。


入力例1

4 5 2
xoooo
oooox
ooooo
oxxoo

出力例1

3

以下の 3 通りが考えられます (o は白いマス、x は黒いマス、* は緑色のマスを表します)。

x*ooo
***ox
o*ooo
oxxoo

xo*oo
o***x
oo*oo
oxxoo

xoooo
ooo*x
oo***
oxx*o

入力例2

4 5 2
ooooo
oxoox
oooox
oxxoo

出力例2

0

入力例3

8 6 3
oooooo
oooooo
oooooo
oooooo
oxoooo
oooooo
oooooo
oooooo

出力例3

4