격자 위에서 단어 만들기

한 농부가 대문자 알파벳으로 채워진 $H \times W$ 크기의 격자를 놓아두었다 ($1 \le H \le 30$, $1 \le W \le 30$). 소는 칸에서 칸으로 뛰어다니며 지나간 순서대로 글자를 읽어 단어를 만든다.

소는 아무 칸에서나 출발할 수 있다. 다만 현재 칸에서 다른 칸으로 뛸 때는 오른쪽 또는 위쪽(혹은 둘 다)에 있는 칸으로만 갈 수 있고, 왼쪽이나 아래쪽 칸으로는 갈 수 없다. 격자의 첫 번째 줄이 맨 위 줄이므로 "위쪽"은 줄 번호가 더 작은 쪽을 뜻한다. 소는 뛰어난 점프 실력을 지녔으므로 한 번의 점프로 임의의 거리를 이동할 수 있다.

경로란 소가 지나간 칸들의 정확한 순서를 말한다. 경로는 칸 하나만으로 이루어질 수도 있으며, 이때 그 칸에 적힌 한 글자짜리 단어를 만든 것으로 본다. 모든 점프가 반드시 오른쪽 또는 위쪽으로만 이동하므로 한 경로에서 같은 칸을 두 번 지나는 일은 없다. 서로 다른 두 경로가 같은 단어를 만들 수는 있지만, 두 소가 완전히 똑같은 경로를 지날 수는 없다.

격자와 유효한 단어 목록이 주어진다. 어떤 경로를 따라 지나간 순서대로 읽은 글자들이 어떤 단어와 정확히 일치하면, 그 경로는 그 단어를 만든 것이다. 목록의 단어를 만드는 서로 다른 경로가 몇 개인지 세어라. 각 소는 서로 다른 경로를 지나야 하므로, 이 개수가 들어갈 수 있는 소의 최대 마리 수이다.

예를 들어 TO를 만들려면, T 위에 서 있는 소는 같은 줄에서 오른쪽에 있거나 더 위쪽 줄에 있는 O(오른쪽, 바로 위, 또는 오른쪽 위)로 뛸 수 있다. 왼쪽이나 아래쪽에 있는 O에는 결코 도달할 수 없다.

• 첫째 줄: 두 정수 $H$와 $W$.
• 둘째 줄부터 $H+1$째 줄까지: 각 줄은 공백 없이 $W$개의 대문자(A–Z)로 이루어지며 격자의 한 행을 나타낸다. 이 중 첫 줄이 맨 위 행이고, 각 줄의 첫 글자가 가장 왼쪽 칸이다.
• $H+2$째 줄: 정수 $N$ ($N \ge 1$), 유효한 단어의 개수.
• 이어지는 $N$개의 줄: 한 줄에 하나씩, 대문자(A–Z)로 이루어진 유효한 단어. 중복된 단어는 하나로 취급한다.

• 한 줄에 정수 하나: 목록의 단어를 만드는 서로 다른 경로의 개수(즉, 어떤 두 소도 같은 경로를 공유하지 않고 들어갈 수 있는 소의 최대 마리 수)를 출력한다.