拉丁字母路径

题目背景

古拉丁字母表由 $21$ 个字母组成：

A B C D E F Z H I K L M N O P Q R S T V X

现在给定一张由这些字母和空格子组成的字符迷宫。你需要统计其中有多少条路径，能够恰好经过这 $21$ 个字母各一次。

题目描述

给定一个包含 $N$ 行、$M$ 列的字符矩阵。矩阵中的每个格子满足以下两种情况之一：

• 包含古拉丁字母表中的一个字母；
• 是空格子，用字符 . 表示。

一条路径是一个格子序列，满足序列中相邻的两个格子在矩阵中上下或左右相邻。路径中不能重复经过同一个格子。

如果一条路径满足：

• 恰好包含 $21$ 个格子；
• 上述 $21$ 个古拉丁字母在路径中各出现恰好一次；

则称它为一条 拉丁字母路径。路径中字母出现的顺序没有限制。

请计算矩阵中拉丁字母路径的总数。

两条路径被视为不同，当且仅当存在某个位置，使得两条路径在该位置经过的格子坐标不同。

因此，同一条无向路径按照相反方向经过时，通常会被计为两条不同的路径。

输入格式

第一行包含两个整数 $N,M$，分别表示矩阵的行数和列数。

接下来 $N$ 行，每行包含一个长度为 $M$ 的字符串，描述字符矩阵。

输出格式

输出一个整数，表示拉丁字母路径的总数。

保证答案可以使用 C++ 的 long long 类型存储。

样例

样例输入 #1

2 20
ABCDEFZHIXKLMNOPQRST
...................V

样例输出 #1

2

样例解释 #1

可以从字母 A 所在格子出发，一直向右走到字母 T，再向下走到字母 V。

按照相反方向从 V 走到 A 也是一条不同的拉丁字母路径，因此答案为 $2$。

样例输入 #2

20 20
ABCDEFZHIXKLMNOPQRST
BCDEFZHIXKLMNOPQRSTV
CDEFZHIXKLMNOPQRSTVA
DEFZHIXKLMNOPQRSTVAB
EFZHIXKLMNOPQRSTVABC
FZHIXKLMNOPQRSTVABCD
ZHIXKLMNOPQRSTVABCDE
HIXKLMNOPQRSTVABCDEF
IXKLMNOPQRSTVABCDEFZ
XKLMNOPQRSTVABCDEFZH
KLMNOPQRSTVABCDEFZHI
LMNOPQRSTVABCDEFZHIX
MNOPQRSTVABCDEFZHIXK
NOPQRSTVABCDEFZHIXKL
OPQRSTVABCDEFZHIXKLM
PQRSTVABCDEFZHIXKLMN
QRSTVABCDEFZHIXKLMNO
RSTVABCDEFZHIXKLMNOP
STVABCDEFZHIXKLMNOPQ
TVABCDEFZHIXKLMNOPQR

样例输出 #2

199229440

样例输入 #3

20 20
ABCABCABCABCABCABCAB
DEFDEFDEFDEFDEFDEFDE
ZHIZHIZHIZHIZHIZHIZH
XKLXKLXKLXKLXKLXKLXK
MNOMNOMNOMNOMNOMNOMN
PQRPQRPQRPQRPQRPQRPQ
STVSTVSTVSTVSTVSTVST
ABCABCABCABCABCABCAB
DEFDEFDEFDEFDEFDEFDE
ZHIZHIZHIZHIZHIZHIZH
XKLXKLXKLXKLXKLXKLXK
MNOMNOMNOMNOMNOMNOMN
PQRPQRPQRPQRPQRPQRPQ
STVSTVSTVSTVSTVSTVST
ABCABCABCABCABCABCAB
DEFDEFDEFDEFDEFDEFDE
ZHIZHIZHIZHIZHIZHIZH
XKLXKLXKLXKLXKLXKLXK
MNOMNOMNOMNOMNOMNOMN
PQRPQRPQRPQRPQRPQRPQ

样例输出 #3

5338808

样例输入 #4

20 20
ABCDEFZABCDEFZABCDEF
HIXKLMNHIXKLMNHIXKLM
OPQRSTVOPQRSTVOPQRST
ABCDEFZABCDEFZABCDEF
HIXKLMNHIXKLMNHIXKLM
OPQRSTVOPQRSTVOPQRST
ABCDEFZABCDEFZABCDEF
HIXKLMNHIXKLMNHIXKLM
OPQRSTVOPQRSTVOPQRST
ABCDEFZABCDEFZABCDEF
HIXKLMNHIXKLMNHIXKLM
OPQRSTVOPQRSTVOPQRST
ABCDEFZABCDEFZABCDEF
HIXKLMNHIXKLMNHIXKLM
OPQRSTVOPQRSTVOPQRST
ABCDEFZABCDEFZABCDEF
HIXKLMNHIXKLMNHIXKLM
OPQRSTVOPQRSTVOPQRST
ABCDEFZABCDEFZABCDEF
HIXKLMNHIXKLMNHIXKLM

样例输出 #4

5338808

样例输入 #5

20 20
ABCDEABCDEABCDEABCDE
FZHIXFZHIXFZHIXFZHIX
KLMNOKLMNOKLMNOKLMNO
PQRSTPQRSTPQRSTPQRST
VABCDVABCDVABCDVABCD
ABCDEABCDEABCDEABCDE
FZHIXFZHIXFZHIXFZHIX
KLMNOKLMNOKLMNOKLMNO
PQRSTPQRSTPQRSTPQRST
VABCDVABCDVABCDVABCD
ABCDEABCDEABCDEABCDE
FZHIXFZHIXFZHIXFZHIX
KLMNOKLMNOKLMNOKLMNO
PQRSTPQRSTPQRSTPQRST
VABCDVABCDVABCDVABCD
ABCDEABCDEABCDEABCDE
FZHIXFZHIXFZHIXFZHIX
KLMNOKLMNOKLMNOKLMNO
PQRSTPQRSTPQRSTPQRST
VABCDVABCDVABCDVABCD

样例输出 #5

2296264

样例输入 #6

4 20
ABCDEFZHIXKLMNOPQRST
..A...............SV
V.B...............T.
ABCDEFZHIXKLMNOPQRST

样例输出 #6

8

样例输入 #7

5 20
.................VT.
....................
ABCDEFZHIXKLMNOPQRS.
..................S.
.................VT.

样例输出 #7

0

样例输入 #8

2 11
TBCDE.PQRSA
FZHIXKLMNOV

样例输出 #8

50

样例输入 #9

6 7
ABCDEF.
V....Z.
T....H.
S....I.
R....X.
KLMNOPQ

样例输出 #9

4

样例输入 #10

4 9
NTCDEFZHI
XKLMAOPQR
SBV......
.........

样例输出 #10

128

数据范围

• $1\le N,M\le 21$；
• 所有输入行长度均为 $M$；
• 每个格子只可能是 .，或者字符 A B C D E F Z H I K L M N O P Q R S T V X 中的一个；
• 上述 $21$ 个字母中的每一个都至少在矩阵中出现一次；
• 答案不超过有符号 $64$ 位整数的表示范围。