문제
다음과 같은 편지격자가 있을 때
격자에서 "TARTU"라는 단어를 읽는 방법이 다음과 같이 7가지가 있다.
편지격자와 단어가 주어지면, 단어을 읽는 방법이 몇 가지가 있는지 찾으시오. 단어의 첫 글자는 격자의 아무칸이나 가능하고, 그 다음 문자는 이웃 하는 칸(가로, 세로, 대각선)이어야 한다. 단어를 읽을 때 격자칸을 여러번 사용할 수 있다.
입력
입력의 첫줄에 격자의 행 R(1≤R≤200), 칸 C(1≤C≤200), 단어의 길이 L(1≤L≤100)가 주어지고, R줄에 걸쳐 C개의 문자가 공백 없이 들어온다. 마지막줄에는 읽을 단어가 들어온다. 모든 문자는 영어 대문자이다.
출력
단어를 읽을수 있는 가지수를 한 줄에 출력한다. 답은 10^18이내이다.
예제1
입력
3 4 5
ERAT
ATSR
AUTU
TARTU
출력
7
힌트
출처
BOI 2010 Practice