问题描述

有一个 $R$ 行 $C$ 列的矩形区域。将第 $i (1 \leq i \leq R)$ 行、第 $j (1 \leq j \leq C)$ 列的格子称为格子 $(i, j)$。这些格子中的一些格子被涂黑，其他格子被涂白。

此外，给定一个整数 $K$。

现在考虑如何涂上绿色，使得以下条件成立。这个操作只进行一次。

• 对于某对整数 $x (K \leq x \leq R - K + 1)$ 和 $y (K \leq y \leq C - K + 1)$，对于满足条件 $|i-x|+|j-y| \leq K - 1$ 的所有格子 $(i,j)$，如果格子 $(i,j)$ 是最初是白色的格子，则在这个操作中格子 $(i,j)$ 被涂成绿色。另外，对于满足条件 $|i-x|+|j-y| \geq K$ 的所有格子，这些格子不会被涂上绿色。

有多少种满足上述涂色规则的涂色方法？这里所说的涂色方法指的是每个格子是什么颜色的组合，不考虑涂色的顺序。

---

输入

输入以以下格式从标准输入中给出。

$R$ $C$ $K$ $s_1$ $s_2$ : $s_R$

• 第一行包含三个整数 $R (3 \leq R \leq 500)$, $C (3 \leq C \leq 500)$, $K (2 \leq K \leq 500)$，以空格分隔。这表示矩形区域有 $R$ 行 $C$ 列，并且给定了整数 $K$。
• 接下来的 $R$ 行给出与每个格子相关的信息。对于第 $i (1 \leq i \leq R)$ 行，给出长度为 $C$ 的字符串 $s_i$。字符串 $s_i$ 由两种字符 o 和 x 构成，$s_i$ 中的第 $j (1 \leq j \leq C)$ 个字符表示格子 $(i,j)$ 是白色还是黑色，如果 $s_i$ 的第 $j$ 个字符为 o，则表示格子 $(i,j)$ 是白色，如果为 x 则表示格子 $(i,j)$ 是黑色。

部分分

此问题设置了部分分。

• 如果通过了数据集 $1$，满足条件 $R \leq 50$ 且 $C \leq 50$，将得到 $30$ 分。

输出

在一行中输出满足涂色规则的涂色方法的总数。输出末尾要换行。

---

输入示例1

4 5 2
xoooo
oooox
ooooo
oxxoo

输出示例1

3

有以下 $3$ 种可能的涂色方法（o 表示白色格子，x 表示黑色格子，* 表示绿色格子）：

x

*

o

o

o

*

*

*

o

x

o

*

o

o

o

o

x

x

o

o

x

o

*

o

o

o

*

*

*

x

o

o

*

o

o

o

x

x

o

o

x

o

o

o

o

o

o

o

*

x

o

o

*

*

*

o

x

x

*

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