该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

CodingCow 坐着电梯下到了一楼。突然，他猛地发现一位熟悉的身影：

这是一位戴着黑框眼镜、身穿灰色西服套装及蓝底白点衬衣的男性演讲者。他在台上手持两只不同款式与色彩搭配的手持设备——左方为一款粉色调的产品，右方则是呈现自上而下的紫到黑渐变效果的设计风格。 这位先生面带微笑地向观众们介绍手中的两款电子产品, 可能是在进行一场关于新产品的发布会或者演示会。通过其自信而又亲民的表情姿态可以感受到他对所展示物品有着深厚的理解以及热爱之情。没错，这位就是 余承东 ！作为一名忠实的花粉，CodingCow 一定要先过去看看再拿外卖！

题目描述

现在已知办公楼的大堂就像一个矩形方阵（大小为 $n \times m$），CodingCow 刚下电梯，站在 $(1,\,1)$ 点，而余承东刚刚从门口走进来，站在 $(n,\,m)$ 点。由于余承东是在是在受欢迎了，大堂聚集了很多人，所以 CodingCow 必须绕行前往余承东所在的位置，但是 CodingCow 现在还没有吃饭，肚子很饿因此他要尽可能减少体力的消耗。众所周知，转向时很消耗体力的，所以，CodingCow 最多只能转向 $t$ 次（可以不转），求 CodingCow 找到余承东有多少种不同的路径。注意，CodingCow 只能向右或下走，并且不走回头路。

输入格式

第一行三个整数 $n$，$m$，$t$，如题目描述。

接下来是一个 $n \times m$ 的字符矩阵，其中 . 代表正常的路，# 代表人群。

输出格式

输出一个数，即所求的 CodingCow 的路径数对 $1000000007$ 取模的值。

样例

3 3 1
...
...
...

2

4 4 3
...#
.#..
....
#...

6

见 "sample_problem4.zip/sample/2.in"

见 "sample_problem4.zip/sample/2.ans"

提示

该题数据量较大，可能需要使用较快的读写方式。

寄语

“摇滚时间到！为反叛高歌！听我最强音！”

附件

sample_problem4.zip。

数据范围

对于 $20\,\%$ 的数据 $1 \leq n,\,m \leq 5$。

对于 $60\,\%$ 的数据 $1 \leq n,\,m\leq 50$。

对于 $100\,\%$ 的数据 $1 \leq n,\,m\leq 248$，$1\leq t \leq \min(n, m)$。

此外，有 $10\,\%$ 的数据 $t = 1$，均匀分布在各档数据中。