题目描述

在无限二维整数网格上，每个格子只有“存活”和“死亡”两种状态。

每一秒，所有格子同时按照下面的规则更新：

对于任意格子 $C$，考虑它自身以及与它上下左右相邻的四个格子，共 5 个格子。如果当前这 5 个格子中存活格子的数量为奇数，则下一秒 $C$ 存活；否则下一秒 $C$ 死亡。

给定一个有限矩形区域的初始状态。矩形外的所有格子初始均为死亡。求经过 $K$ 秒后整个无限平面上共有多少个存活格子。

输入格式

第一行三个整数 $H$、$W$、$K$，分别表示初始矩形的行数、列数和演化时间。

接下来 $H$ 行，每行一个长度为 $W$ 的字符串：

• o 表示该格子初始存活；
• . 表示该格子初始死亡。

输出格式

输出一个整数，表示 $K$ 秒后存活格子的总数。

数据范围

• $1\le H,W\le 50$；
• $1\le K\le 10^9$；
• 答案保证可以用有符号 64 位整数表示。

样例 1

输入

2 2 3
oo
o.

输出

23