### 问题描述 传说，在蓝桥王国中一个极其神秘的森林。这个森林的起点在 $(1, 1)$ ，终点在 $(n, m)$。在你进入这个森岭后，每次你只可以向下或者向右走，由于森岭的神秘力量，至多只可以改变 $k$ 次方向。 小蓝现在想知道，一共有多少种方案可以从 $(1, 1)$ 进入然后从 $(n, m)$ 走出。数据保证至少存在一种方案。 ### 输入格式 第 $1$ 行包含三个正整数 $n, m, k$，分别表示地图的规模和可以改变方向的次数。 第 $2$ 到 $n + 1$ 行包含 $m$ 个字符，表示地图上该位置的信息，用```.```表示空地，```#```表示石头无法通行，保证起点和终点不为石头。 ### 输出格式 输出共 $1$ 行，包含 $1$ 个整数，表示方案数。 ### 样例输入 ```text 3 3 1 ... .#. ... ``` ### 样例输出 ```text 2 ``` ### 评测数据规模 对于所有评测数据，$1\leq n,m \leq 100$，$1 \le k \le 5$。