단어 찾기

$N \times M$ 크기의 표가 있고, 각 칸에는 알파벳 대문자가 하나씩 쓰여 있다. 단어 $S$가 주어졌을 때, 표에 단어 $S$가 있는지 없는지 구하는 프로그램을 작성하시오.

표에 단어 $S$가 있으려면 표의 한 칸에서 시작해 $S$의 알파벳이 순서대로 이웃한 칸에 이어져야 한다. 이어지는 방향은 위, 아래, 왼쪽, 오른쪽과 대각선 네 방향인 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래를 모두 쓸 수 있다. 단, 중간에 방향을 바꾸면 안 된다.

첫째 줄에 단어 $S$가 주어진다. $S$의 길이는 100보다 작거나 같고, $S$는 알파벳 대문자로만 이루어져 있다.

둘째 줄에 표의 행의 개수 $N$과 열의 개수 $M$이 주어진다. $N$과 $M$은 100보다 작거나 같은 자연수이다.

셋째 줄부터 $N$개의 줄에 표의 각 행에 들어 있는 알파벳이 $M$개씩 공백 없이 주어진다.

표에 단어 $S$가 있으면 1을, 없으면 0을 출력한다.