Letter Board

There is an N×M board with one uppercase English letter written in each cell.

For illustration, consider this board:

Choose any cell as the starting cell. As you move from cell to cell, the letters written on the visited cells are read in order to form a word. On each move, you may move vertically or horizontally by at least 1 and at most K cells.

When K=2, a cell in the center can move to the cells marked X below:

You must move at least one cell, so staying in the same cell is not allowed. The same cell may be visited more than once.

Given the board, K, and one English word, write a program that counts how many paths can form that word.

In the board above, the word BREAK can be formed by 3 paths. Each pair below is written as row number followed by column number.

• (4, 2) (3, 2) (2, 2) (1, 2) (1, 1)
• (4, 2) (3, 2) (2, 2) (1, 2) (1, 3)
• (4, 2) (3, 2) (2, 2) (2, 3) (1, 3)

The first line contains N (1 ≤ N ≤ 100), M (1 ≤ M ≤ 100), and K (1 ≤ K ≤ 5).

Each of the next N lines contains M uppercase English letters, describing the N×M board.

The next line contains the target English word. Its length is between 1 and 80, inclusive. All letters are uppercase English letters, and there are no spaces.

Print the number of paths on the first line. This value is at most 2^31 - 1.