On a given facade, windows are organized on a rectangular grid with $N$ rows and $M$ columns. Anne has gathered a list of size $A$ of $N$-letter words and a list of size $B$ of $M$-letter words. She is wondering how many ways there are to display simultaneously $N$ words of length $M$ horizontally and $M$ words of length $N$ vertically on that grid.
The input consists of the following:
*Limits*
The input satisfies $2 <= N$, $M <= 4$ and $1 <= A times B <= 1008016$.
Words are taken from the English dictionary. Each of the two lists contains no repetition. Words consist of lowercase letters between 'a' (ASCII code 97) and 'z' (ASCII code 122).
Words from the first list will be displayed vertically, from top to bottom. Words from the second list will be displayed horizontally, from left to right. The same word can be used several times to build a grid, i.e., in several columns (resp., rows) if it belongs to the first (resp., second) list of words.
When $N = M$, it is not allowed to use words from the first list horizontally (unless they appear in the second list as well), or words from the second list vertically (unless they appear in the first list as well).
The output should consist of a single line, whose content is an integer, the total number of distinct word grids.
*Sample Explanation 1*
The solutions are:
*Sample Explanation 2*
The solutions are:
## Input
The input consists of the following: The first line contains two integers N and A separated with a single space. The second line contains two integers M and B separated with a single space. The next A lines contains N-letter words, one per line. The next B lines contains M-letter words, one per line. *Limits*The input satisfies $2 <= N$, $M <= 4$ and $1 <= A times B <= 1008016$.Words are taken from the English dictionary. Each of the two lists contains no repetition. Words consist of lowercase letters between 'a' (ASCII code 97) and 'z' (ASCII code 122).Words from the first list will be displayed vertically, from top to bottom. Words from the second list will be displayed horizontally, from left to right. The same word can be used several times to build a grid, i.e., in several columns (resp., rows) if it belongs to the first (resp., second) list of words.When $N = M$, it is not allowed to use words from the first list horizontally (unless they appear in the second list as well), or words from the second list vertically (unless they appear in the first list as well).
## Output
The output should consist of a single line, whose content is an integer, the total number of distinct word grids.
[samples]
## Note
*Sample Explanation 1*The solutions are: *Sample Explanation 2*The solutions are:
**Definitions**
Let $ N, M \in \mathbb{Z} $ be the number of rows and columns of the grid, respectively.
Let $ V = \{v_1, v_2, \dots, v_A\} $ be a set of $ A $ distinct $ N $-letter words (vertical words).
Let $ H = \{h_1, h_2, \dots, h_B\} $ be a set of $ B $ distinct $ M $-letter words (horizontal words).
**Constraints**
1. $ 2 \leq N, M \leq 4 $
2. $ 1 \leq A \cdot B \leq 1008016 $
3. All words consist of lowercase English letters.
4. If $ N = M $, then $ V \cap H = \emptyset $ for cross-use:
- Words in $ V $ cannot be used horizontally unless $ v \in H $,
- Words in $ H $ cannot be used vertically unless $ h \in V $.
**Objective**
Count the number of $ N \times M $ grids such that:
- Each row $ i \in \{1, \dots, N\} $ is assigned a word $ h_{j_i} \in H $ (horizontal),
- Each column $ j \in \{1, \dots, M\} $ is assigned a word $ v_{k_j} \in V $ (vertical),
- For all $ i \in \{1, \dots, N\}, j \in \{1, \dots, M\} $, the character at position $ (i,j) $ matches:
$$
v_{k_j}[i] = h_{j_i}[j]
$$
That is, the grid is consistent with both row and column word assignments.
The total number of such consistent grids is:
$$
\left| \left\{ (h_1, \dots, h_N) \in H^N,\ (v_1, \dots, v_M) \in V^M \ \middle|\ \forall i,j,\ h_i[j] = v_j[i] \right\} \right|
$$