크로스워드

파리에서 관광객을 더 끌어들이기 위해 앤은 루브르 궁전의 외벽에서 밤마다 대규모 빛과 소리 쇼를 열려고 한다. 외벽에는 여러 층에 창문이 있고, 창문들은 세로로도 줄을 맞춰 배치되어 있다. 앤은 창문 하나에 글자 하나씩 거대한 글자를 띄워서, 가로와 세로 방향으로 모두 단어가 되도록 하려고 한다.

외벽의 창문은 N개의 행과 M개의 열로 이루어진 직사각형 격자를 이룬다. 앤은 길이가 N인 단어 A개의 목록과 길이가 M인 단어 B개의 목록을 가지고 있다. 길이가 M인 단어 N개를 가로로, 길이가 N인 단어 M개를 세로로 동시에 격자에 표시하는 방법이 몇 가지인지 구하라.

첫 번째 목록의 단어는 위에서 아래로 세로로 표시한다. 두 번째 목록의 단어는 왼쪽에서 오른쪽으로 가로로 표시한다. 첫 번째 목록에 있는 단어는 여러 열에 사용할 수 있고, 두 번째 목록에 있는 단어는 여러 행에 사용할 수 있다.

N과 M이 같으면, 첫 번째 목록의 단어는 두 번째 목록에도 들어 있지 않는 한 가로로 사용할 수 없다. 마찬가지로 두 번째 목록의 단어는 첫 번째 목록에도 들어 있지 않는 한 세로로 사용할 수 없다.

첫 번째 줄에는 정수 N과 A가 공백 하나로 구분되어 주어진다.

두 번째 줄에는 정수 M과 B가 공백 하나로 구분되어 주어진다.

다음 A줄에는 길이가 N인 단어가 한 줄에 하나씩 주어진다.

그다음 B줄에는 길이가 M인 단어가 한 줄에 하나씩 주어진다.

서로 다른 단어 격자의 총개수를 나타내는 정수 하나를 한 줄에 출력한다.

$2 \le N, M \le 4$이고 $1 \le A \times B \le 1008016$이다.

단어는 영어 사전에서 가져온다. 각 목록에는 같은 단어가 두 번 들어 있지 않다. 단어는 소문자 a(ASCII 97)부터 z(ASCII 122)까지의 글자로만 이루어진다.