/*
* Problem :: 2186 / 문자판
*
* Kind :: Dynamic Programming
*
* Insight
* - 브루트 포스로 풀려고 했다가 틀렸다
* + max(N)=100 이고 max(M)=100 이라 상대적으로 작아보이지만
* K 와 한글자로 이루어진 영단어를 생각해보면 엄청난 시간복잡도가 나오게 된다
* # 최악의 경우를 생각해보면
* N=100, M=100, K=5 이고
* 모든 문자판이 'B'로 이루어져 있으며
* 영단어=BBB...BBB(80자) 라고 하자
* 이경우, 시간복잡도는 O(NM*(20^80)) 가 나온다
* -> 당연히 시간초과다
*
* - 예제 입력 1 과 같이 주어졌다고 하자
* 문자판에서 (1,1) 이 'K' 이며 주어진 영단어 "BREAK" 의 마지막 글자도 'K' 이다
* 가능한 모든 경우중에서 (1,1) 의 'K' 로 끝나는 경우의 수를 알아낼 수 없을까?
* + 이를 다음과 같이 표현할 수 있다
* dp[1][1][4] = (1,1) 의 문자를 마지막문자로 하며,
* 영단어.substr(0,5) 를 만들 수 있는 경우의 수
* # 이를 일반화하면
* dp[i][j][idx] = (i,j) 의 문자를 마지막문자로 하며
* 영단어.substr(0,idx+1) 을 만들 수 있는 경우의 수
* -> 그냥 찾으면 시간초과지만,
* 각 칸의 글자가 주어진 영단어에서 몇번째에 위치하는 것이 가능한지
* 그 경우의 수를 알아낼 수 있다면 DP 를 이용해서 최적화가 가능하다!
* => (i,j) 에서 이동가능한 임의의 칸을 (y,x) 라 하면
* dp[i][j][idx] += dp[y][x][idx-1]
*
* Point
* - 최악의 경우를 생각하는 것이 중요하다
*
* - i번째 글자는 인덱스로는 (i-1)이다
*/
//
// BOJ
// ver.C++
//
// Created by GGlifer
//
// Open Source
#include <iostream>
#include <cstring>
using namespace std;
#define endl '\n'
// Set up : Global Variables
int N, M, K;
char A[100][100];
int dp[100][100][80];
string W;
int dy[4] = {+1, 0, 0, -1};
int dx[4] = {0, +1, -1, 0};
// Set up : Functions Declaration
bool isValid(int y, int x);
int f(int cy, int cx, int idx);
int main()
{
// Set up : I/O
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Set up : Input
cin >> N >> M >> K;
for (int i=0; i<N; i++)
for (int j=0; j<M; j++)
cin >> A[i][j];
cin >> W;
// Process
memset(dp, -1, sizeof(dp));
int ans = 0;
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
/* (i,j) 의 문자와 영단어의 마지막 문자가 같다면 */
if (A[i][j] == W.back()) {
/* (i,j) 의 문자를 마지막으로 하며 영단어를 만들 수 있는 경우의 수를 더함 */
ans += f(i, j, W.length()-1);
}
}
}
// Control : Output
cout << ans << endl;
}
// Helper Functions
bool isValid(int y, int x)
/* 주어진 좌표 (y,x) 가 유효하면 true 를 반환, 그 외 false 를 반환 */
{
return y >= 0 && y < N && x >= 0 && x < M;
}
int f(int cy, int cx, int idx)
/* dp[cy][cx][idx] 값을 반환
* = (cy,cx) 의 문자를 마지막문자로 하며,
* 영단어.substr(0,idx+1) 을 만들 수 있는 경우의 수를 반환 */
{
if (idx == 0) return 1; /* 가능한 경우를 찾음 */
if (dp[cy][cx][idx] != -1) return dp[cy][cx][idx];
dp[cy][cx][idx] = 0;
for (int i=0; i<4; i++) {
for (int k=1; k<=K; k++) {
int py = cy + k*dy[i];
int px = cx + k*dx[i];
/* (py,px) 가 이동가능하지 않으면 넘어감 */
if (not(isValid(py, px))) break;
/* (px,py) 에 써진 글자가 영단어의 idx번째 글자와 일치하지 않으면 넘어감 */
if (not(A[py][px] == W[idx-1])) continue;
dp[cy][cx][idx] += f(py, px, idx-1);
}
}
return dp[cy][cx][idx];
}