题目描述

农夫约翰为他的奶牛设置了一个谜题来解决。在谷仓的入口处，他布置了一个 $\red{H \times W (1 <= H <= 30, 1 <= W <= 30) }$字母网格。在母牛可以进入谷仓之前，她必须通过 从一个方块跳到另一个方块，拼出一个有效的英文单词，创建一个字母序列。

她可以从任何方格开始，但只能跳到位于当前方格右侧和$\red{/}$或上方的后续方格（即，既不向左也不向下）。下一个方格可以与当前方格有任何距离，因为奶牛是世界级的跳投者！没有两头奶牛可以穿过完全相同的路径，尽管允许两头奶牛通过不同的路径拼写同一个单词。

例如，考虑这个网格（假设 '$\red{TO}$' 和 '$\red{OX}$' 是单词）： $\red{T X X O T X Q T X T X Q }$四个路径都是有效的，所有拼写都是 '$\red{TO}$'（一个拼写需要 底部行中的 '$\red{T}$' 和底部行中的 '$\red{O}$'顶行）。 '$\red{OX}$' 是一个有效的单词，但需要跳转到'$\red{O}$' 左侧的'$\red{X}$' 方格，这是不允许的。

给定网格和有效单词列表，计算在没有任何奶牛重复路径的情况下可以进入谷仓的奶牛数量。 ## 输入格式

第 $\red{1 }$行：两个整数：$\red{H }$和 $\red{W }$

第 $\red{2..H+1 }$行：每行包含 $\red{W }$个字符，不包含空格，表示网格中的一行。第一行是顶行。每行中的第一个字符是最左边的字符。

输出格式

第 $\red{1 }$行：无需重复路径即可进入牛舍的奶牛数量。

样例

输入样例

3 4
TXXO
TXQT
XTXQ

输出样例

4

提示

输出详细信息：

$\red{4}$头牛可以进入牲口棚，每头牛都会拼写出一个"$\red{TO}$"