瞬移

题目描述

在一个 $n \times m$ 的迷宫中，小 H 拥有瞬移的能力。他可以从当前所在的格子瞬间移动到地图上任何一个未访问过的非虚空（'E'）格子上。

迷宫中的格子有以下几种类型：

• 'A': 起点，固定在左上角 $(1, 1)$。
• 'B': 终点，固定在右下角 $(n, m)$。
• 'C': 普通格子。
• 'D': 更改器。地图上最多只有一个。
• 'E': 虚空。

游戏规则如下：

1. 小 H 从起点 'A' 出发，目标是到达终点 'B'。
2. 每次当小 H 从一个格子瞬移离开后，该格子会立即坍塌，变为虚空 'E'。
3. 瞬移的目标格子不能是虚空（无论是初始的还是坍塌后的）。如果瞬移到虚空，则该路径失败。
4. 如果小 H 瞬移到类型为 'D' 的格子上，他会获得一个“更改器”。这个更改器可以使用一次，作用是将地图上任意一个初始为 'E' 的格子变为普通格子 'C'，从而使其可以被访问。

请你计算，小 H 从起点 'A' 到达终点 'B' 有多少条不同的胜利路径。一条路径被定义为一个瞬移的格子序列。

输入格式

第一行输入两个正整数 $n, m$。

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

输出格式

输出一个整数，表示胜利路径的总数。

样例

样例输入 1

2 2
AC
EB

样例输出 1

2

样例输入 2

2 3
AEE
EDB

样例输出 2

5

提示

数据范围与约定

• $2 \le n, m \le 5$
• 地图保证有且仅有一个 'A' 和一个 'B'，分别位于左上角和右下角。
• 地图中最多只有一个 'D'。

题目原创自zhixing