CCC Word Hunt

문제

In the CCC Word Hunt, words are hidden in a grid of letters. The letters of a hidden word always appear in order on horizontal, vertical, or diagonal line segments in one of two ways. One way is for the letters of a word to appear on one line segment. The other way is for the letters of a word to appear on one line segment up to some letter and then on a second line segment that forms a right angle at this letter.

Given a grid of letters and a single word to search for, your job is to determine the number of times that particular word is hidden in the grid.

입력

The first line of input will contain a string of distinct uppercase letters, $WW$, representing the word you are to search for in the grid. The length of $WW$ will be at least two.

The second line of input will be an integer $RR$ $(1\le R\le 100)(1\; \backslash le\; R\; \backslash le\; 100)$, where $RR$ is the number of rows in the grid.

The third line of input will be an integer $CC$ $(1\le C\le 100)(1\; \backslash le\; C\; \backslash le\; 100)$, where $CC$ is the number of columns in the grid.

The remaining input will provide the letters in the grid. It will consist of $RR$ lines, where each line contains $CC$ uppercase letters separated by single spaces.

출력

The output will consist of a single non-negative integer $HH$, representing the number of times the word is hidden in the grid.

MENU
5
7
F T R U B L K
P M N A X C U
A E R C N E O
M N E U A R M
M U N E M N S

3

NATURE
6
9
N A T S F E G Q N
S A I B M R H F A
C F T J C U C L T
K B H U P T A N U
D P R R R J D I R
I E E K M E G B E

4