T579308 【2025 年 3 月月赛赛题 D】交错路径

[Hydro 域链接](https://hydro.ac/d/chenyuan3_s_online_judge/p/Contest202503D) 本题由 DeepSeek 生成，并由 @[chenyuan3](/user/559528) 完善。[题解](https://chenyuan33a.freeflarum.com/d/58) upd 2025/03/04：修复样例 2 输出，并给提示/说明加上样例解释。

在 $n \times m$ 网格中从左上到右下移动，求恰好有 $t$ 次转向的路径数。转向点定义为移动方向变化的位置。如果起点或者终点是墙（字符 `#`），输出 $0$。

第一行三个整数 $n$, $m$, $t$。 接下来 $n$ 行每行 $m$ 个字符，每个字符只能是： * `.` 表示空地； * `#` 表示墙。

输出路径数模 $10^9+7$。

**【样例 1 解释】** 终点是墙，所以答案是 $0$。 **【样例 2 解释】** 只有一种走法：（路线：`a-b-c-d`） ``` a#. bcd ``` **【数据范围】** 对于 $100\%$ 的数据，满足 $1 \le n,m \le 5$，$0 \le t \le 10$，并且网格的每一个字符只能是 `.` 或 `#`。