题目描述

一个展厅可以看成 $N \times M$ 的方格图。地图中 S 表示入口，T 表示出口，# 表示关闭区域，. 表示可以经过的位置。

参观者每次只能向上、下、左、右移动一格，并且每个格子最多经过一次。请计算从入口走到出口的不同路线数。

输入格式

第一行两个整数 $N,M$。

接下来 $N$ 行，每行 $M$ 个字符。保证地图中恰好有一个 S 和一个 T。

输出格式

输出一个整数，表示不同路线数。

样例输入

3 3
S#.
.#.
..T

样例输出

1

数据范围

对于 $100\%$ 的数据，$1 \le N,M \le 5$。