cho.sh
Notes
Loading...

Word Grid

Time limit

1s

Memory limit

128 MB

Problem

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.

Input

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

Output the number of distinct ways to read the given word. The answer does not exceed 10^18.