String Path

There is a rectangular grid of size $N \times M$. Every cell holds one uppercase letter. Rows are numbered 1 to $N$ from top to bottom, and columns are numbered 1 to $M$ from left to right.

Consider a route that starts at $(1, 1)$, moves one cell down or one cell right at each step, and ends at $(N, M)$. Writing every letter of the visited cells in the order they are visited gives a string of length $N+M-1$, and that string is called a string path of the grid. Different routes can give several string paths in one grid.

You are given two different strings of length $N+M-1$. Write a program that counts the rectangular grids for which both strings are string paths. Two grids count as different when some position holds a different letter. The count can be large, so print it modulo 1,000,000,009.

The first line contains two natural numbers $N$ and $M$. ($1 \le N, M \le 8$)

The second line and the third line each contain one string of uppercase letters of length $N+M-1$. The two strings are different.

Print the number of rectangular grids for which both given strings are string paths, modulo 1,000,000,009.

With $N = 2$, $M = 2$ and the strings ABC and ADC, the two grids below satisfy the condition.