Count Word Occurrences in a Grid

You are given a 2D grid of uppercase English letters and a target word. Your task is to find the number of occurrences of this word in the grid. An occurrence is defined as a path in the grid that sequentially spells out the word by moving to any of the four adjacent cells (up, down, left, or right). Note that the same cell cannot be used more than once in a single occurrence.

The search is performed as follows:

• Start from any cell that matches the first letter of the word.
• Perform a depth-first search to see if the complete word can be found by moving to adjacent cells.
• If a complete match is found, count that starting cell as one occurrence.

Note: Different occurrences starting from different positions in the grid are counted separately, even if the same group of letters is involved in multiple occurrences.

The answer should be implemented such that it reads from standard input (stdin) and writes the result to standard output (stdout).

inputFormat

The input is given in the following format (read from stdin):

R C
row1
row2
...
rowR
word

Where:

• R and C are integers denoting the number of rows and columns in the grid respectively.
• Each of the next R lines contains a string of C uppercase letters representing a row of the grid.
• The last line contains the target word.

outputFormat

Output a single integer which is the count of occurrences of the target word in the grid. The output should be written to stdout.

## sample

3 4
ABCE
SFCS
ADEE
ABCCED

1