문자판

알파벳 대문자가 한 칸에 하나씩 적힌 N×M 크기의 문자판이 있다.

설명을 위해 다음 문자판을 보자.

아무 칸에서 시작해 칸을 이동하면서, 방문한 칸의 문자를 차례대로 읽으면 하나의 단어를 만들 수 있다. 한 번 이동할 때는 상하좌우 중 한 방향으로 1칸 이상 K칸 이하만큼 이동할 수 있다.

K=2일 때 가운데 칸에서는 아래 그림의 X 표시가 있는 칸으로 이동할 수 있다.

반드시 한 칸 이상 이동해야 하므로 제자리에 머무를 수 없다. 같은 칸은 여러 번 방문해도 된다.

문자판, K, 그리고 하나의 영단어가 주어진다. 이 단어를 만들 수 있는 경로가 모두 몇 개인지 구하는 프로그램을 작성하시오.

위 문자판에서 영단어가 BREAK라면 다음과 같이 3개의 경로가 있다. 각 순서쌍은 행 번호, 열 번호 순서이다.

• (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)

첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다.

다음 N개의 줄에는 N×M 크기의 문자판을 나타내는 M개의 알파벳 대문자가 공백 없이 주어진다.

그다음 줄에는 목표 영단어가 주어진다. 단어의 길이는 1 이상 80 이하이다. 모든 문자는 알파벳 대문자이며, 공백 없이 주어진다.

첫째 줄에 경로의 개수를 출력한다. 이 값은 2^31 - 1 이하이다.