题面：限步迷宫路径

时间限制： 1 秒 内存限制： 256 MB

给定一个 n 行 m 列的迷宫。

迷宫中包含以下字符：

S 表示起点
E 表示终点
. 表示可以通过的空地
# 表示不能通过的墙

你从起点 S 出发，每一步可以向上、下、左、右四个方向之一移动一格。

在一条路径中，同一个格子不能被重复经过。并且整条路径的步数不能超过 limit。

请你计算从 S 到 E 一共有多少条合法路径。

输入格式

第一行包含三个整数 n, m, limit。

接下来 n 行，每行包含一个长度为 m 的字符串，表示迷宫。

输出格式

输出一个整数，表示从起点到终点的合法路径数量。

数据范围

1 <= n, m <= 8
0 <= limit <= 20

保证迷宫中恰好有一个 S 和一个 E。

样例

输入

2 3 4
S..
..E

输出

3

说明

从左上角的 S 出发，在不重复经过格子且步数不超过 4 的条件下，共有 3 条路径可以到达 E。

测试点说明表