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

T3. 花园寻路 (garden)

题目描述

小明家有一个 $N$ 行 $M$ 列的长方形花园。花园中有些格子种了花（用 * 表示），不能踩踏；其余格子是草地（用 . 表示），可以行走。

小明在花园中放置了一个起点（用 S 表示）和一个终点（用 T 表示），起点和终点都在草地上。小明每次可以向上、下、左、右四个方向之一走一步，不能走出花园边界，也不能踩到花上。

小明想知道：从起点走到终点，有多少条不同的简单路径？简单路径是指路径中不重复经过同一个格子的路径。

两条路径只要经过的格子集合不同，或经过的顺序不同，就算不同的路径。

输入格式 garden.in

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

接下来 $N$ 行，每行一个长度为 $M$ 的字符串，由 .、*、S、T 组成，其中 S 和 T 各恰好出现一次。

输出格式 garden.out

一行一个整数，表示不同简单路径的数量。如果数量超过 $10^6$，输出 $10^6$。

样例

样例 #1

3 3
S..
.*.
..T

2

解释：两条路径：S→右→下→下→右→T 和 S→下→右→右→下→T。

样例 #2

2 3
S.T
...

1

解释：只有 S→右→右→T 这一条简单路径。

数据范围

对于全部数据，$1\le N,M\le 20$，空地（含S和T）总数不超过 $30$。