Problem Statement
有一个 n * m 的棋盘， 每个格子上有一个大写字母，
你可以从左上角 (1,1) 出发， 每次只能向下走或者向右走，
走到 (n, m) 。 你走过的路径上的字符顺次相接， 就得到了这个路径对应的字符串。
现在给你两个不同的长为 n + m - 1 的字符串，
已知对于每个给出的字符串， 这个棋盘都存在一条从 (1,1) 到$$(n, m)$$的路径，
使得这条路径对应的字符串， 就是这个字符串。
问有多少种不同的满足条件的棋盘。 两个棋盘不同当且仅当存在某个格子上的字母不同。
数据范围： 1 <= n, m <= 8
Manao has a rectangular board divided into n times m cells.
The rows of the board are numbered from 1 to n and the columns are numbered from 1 to m.
The cell in row i, column j is referred to as (i, j).
Each cell contains an uppercase letter of the English alphabet.
Having such a board, Manao likes to traverse it.
The traversal always starts in the cell (1, 1).
In each step of the traversal Manao moves either one cell down or one cell to the right.
That is, from any cell (x, y) Manao will move either to (x+1, y) or to (x, y+1).
The traversal always ends in the cell (n, m).
During the traversal Manao records the letters in the visited cells (including the first and the last cell).
The obtained string is called a string path for the given board.
You are given the ints n and m, and two distinct Strings A and B.
Manao claims that he performed two different traversals of his n x m board and obtained the string paths A and B.
Compute the number of different boards for which this is possible.
Return this number modulo 1,000,000,009.