AT_code_thanks_festival_2015_h 穴あきケーキ

圣诞节临近，你决定为朋友制作一个独特的有孔圣诞蛋糕。 这个特殊的蛋糕是一个 $R$ 行 $C$ 列的矩形蛋糕坯。我们将矩形的每个位置称为“区域”，例如，第 $i$ 行，第 $j$ 列的位置记为区域 $(i, j)$。如果你吃掉这个区域，你将获取 $C_{i,j}$ 千卡路里。矩形的左上角为区域 $(1, 1)$，右下角为区域 $(R, C)$。 制作有孔蛋糕需要遵循以下步骤： 1. 首先选择四个整数 $a, b, c, d$，要求满足 $1 \le a < b \le R, 1 \le c < d \le C, b - a \ge 2, d - c \ge 2$。接着，从蛋糕坯中切下以 $(a, c)$ 为左上角、$(b, d)$ 为右下角的矩形部分。 2. 在这个矩形部分中，选择一个不位于边界的区域 $(e, f)$，其中 $a+1 \le e \le b-1, c+1 \le f \le d-1$，然后将其挖空，剩下的部分即成为有孔蛋糕。 希望吃这个蛋糕的朋友要求摄入的卡路里恰好为 $K$ 千卡。你的任务是计算出符合条件的有孔蛋糕的所有可能组合，即找到符合以上条件的整数 $a, b, c, d, e, f$ 的所有配置数量。

输入通过标准输入按以下格式给出： - 第一行包含三个整数：$R$ 行数 $(3 \le R \le 350)$、$C$ 列数 $(3 \le C \le 350)$ 以及朋友期望的卡路里量 $K$ $(0 \le K \le 999,999)$。 - 接下来的 $R$ 行，每行一个长度为 $C$ 的字符串 $s_i$，描述蛋糕坯的卡路里信息。字符串 $s_i$ 中的每个字符都是从 `1` 到 `9` 的数字，表示对应区域 $(i, j)$ 的卡路里值 $C_{i,j}$。

输出一个整数，表示符合条件的有孔蛋糕的总数量。在输出结尾处换行。 ## 示例说明 ### 示例说明 1 蛋糕坯如表所示： ``` 1 1 1 1 2 1 7 3 1 2 1 1 1 1 1 9 ``` 例如：选择 $a = 2, b = 4, c = 1, d = 4$，切下的部分为： ``` 1 1 2 1 1 7 3 1 1 1 1 1 ``` 并在 $(e, f) = (3, 2)$ 处挖一个孔，有孔蛋糕的形状为： ``` 1 1 2 1 1 * 3 1 1 1 1 1 ``` 此时总摄入卡路里为 $14$，满足条件。再如：选择 $a = 1, b = 3, c = 3, d = 5, e = 2, f = 4$ 也满足条件。 ### 示例说明 2 即使有孔蛋糕的卡路里分布相同，只要选择的切割位置或者挖孔位置不同，也视为不同的蛋糕。 ### 示例说明 3 有些情况，可能没有满足条件的有孔蛋糕。 **本翻译由 AI 自动生成**

### Sample Explanation 1 ケーキ生地は下表のようになっています。 5 4 3 1 1 1 1 2 1 1 1 7 3 1 2 1 1 1 1 9例えば、$ a $ = $ 2 $, $ b $ = $ 4 $, $ c $ = $ 1 $, $ d $ = $ 4 $ として切り出した場合、以下の領域が切り出されます。 1 1 2 1 1 7 3 1 1 1 1 1さらに、$ e $ = $ 3 $, $ f $ = $ 2 $ として穴を開けると、穴あきケーキは以下の形状となります (`\*` は穴を開けた場所を表す)。 1 1 2 1 1 \\\* 3 1 1 1 1 1このとき、摂取カロリーは、$ 1+1+2+1+1+3+1+1+1+1+1 $ = $ 14 $ となり、条件を満たします。 他にも $ a $ = $ 1 $, $ b $ = $ 3 $, $ c $ = $ 3 $, $ d $ = $ 5 $, $ e $ = $ 2 $, $ f $ = $ 4 $ のときに条件を満たします。 ### Sample Explanation 2 穴あきケーキを構成する領域のカロリーの配置が同じでも、切り出す場所、穴を開ける場所が異なれば異なるケーキとして数えます。 ### Sample Explanation 3 条件を満たす穴あきケーキが存在しない場合もあります。