Time limit
1s
Memory limit
128 MB
You are given an H by W grid filled with uppercase English letters and a word of length L.
The first letter of the word may start at any cell in the grid. For each letter after that, you must move from the previous cell to an adjacent cell. Adjacent cells are the 8 cells in the vertical, horizontal, and diagonal directions. The same cell may be used more than once.
Count the number of distinct ways to read the given word.
The first line contains three integers H, W, and L. H is the height of the grid, W is the width of the grid, and L is the length of the word. (1 <= H, W <= 200, 1 <= L <= 100)
The next H lines each contain a string of length W describing one row of the grid. The last line contains the word of length L. Every character is an uppercase English letter.
Output the number of distinct ways to read the given word. The answer does not exceed 10^18.