F 陷阱

题目描述

总是有小鼠跑进聪明兔的胡萝卜田里偷胡萝卜吃，聪明兔很生气，决定布置陷阱给小鼠一点教训。

聪明兔的胡萝卜田可以看作 $n\times m$ 的网格，聪明兔的小屋在第 $n$ 行的下方，小鼠会从第一行闯入。聪明兔决定提前收获一些胡萝卜，并在空出的位置布满陷阱。为了避免小鼠找到规律，她规定如果格子 $(i,j)$ 是陷阱，那么这一格的左边、右边和上方，也就是格子 $(i,j-1),(i,j+1),(i-1,j)$ 之中陷阱总数不能超过 $k$。

聪明兔希望有些格子必须是胡萝卜，并构思好了一种布置陷阱的方案。闲着没事的兔决定考考你：规定一些格子中必须种胡萝卜的前提下，有多少种布置陷阱的方案。

当两种方案存在至少一个格子的内容物不同，我们认为两种方案不同。另外，不设置陷阱的方案也视作合法方案。答案对 $998244353$ 取模。

输入格式

第一行，三个正整数 $n,m,k$，表示网格的行数、列数，以及对陷阱的限制。

接下来一个 $n$ 行 $m$ 列的矩阵，包含 # 和 . 两种字符。# 表示这一格必须种胡萝卜，. 表示这一格可以种胡萝卜或者放陷阱。

输出格式

输出一行一个整数，表示方案数对 $998244353$ 取模的结果。

输入输出样例

3 3 1
...
.#.
...

168

数据范围

对于 $100\%$ 的数据，满足 $n\times m\le 256,1\le m\le n,0\le k\le 3$。

本题采用捆绑测试。