Baltic Olympiad in Informatics, April 30 – May 3, 2010, Tartu, Estonia

Letter Grid

Consider the following letter grid:

There are 7 ways to read the word TARTU from the grid:

Given a letter grid and a word, your task is to determine the number of ways the word can be read from the grid. The first letter of the word can be in any cell of the grid, and after each letter, the next letter has to be in one of the neighbour cells (horizontally, vertically or diagonally). A cell can be used multiple times when reading the word.

Input Data

The first line of the file grid.in contains three integers: H (1 ≤ H ≤ 200), the height of the grid, W (1 ≤ W ≤ 200), the width of the grid, and L (1 ≤ L ≤ 100), the length of the word. The following H lines each containing W letters describe the grid. The last line containing L letters describes the word. All letters in the grid and in the word are uppercase English letters (A...Z).

Output Data

The only line of the file grid.out should contain one integer: the number of ways the word can be read from the grid. You may assume that the answer is always at most 10¹⁸.

Examples

Browsable version