String Path

Time limit1sMemory limit128 MB

Summary

Count the N by M letter grids where two given strings each appear on a down-right path from the top-left to the bottom-right corner.

Level: Hard8 of 10
Topics: Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Hint

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


A	B
D	C


A	D
B	C

Examples2

Example 1
Input
```
2 2
ABC
ADC
```
Expected output
```
2
```
Example 2
Input
```
1 1
A
B
```
Expected output
```
0
```