{"raw_statement":[{"iden":"statement","content":"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.\n\nThe input consists of the following: \n\n*Limits*\n\nThe input satisfies $2 <= N$, $M <= 4$ and $1 <= A times B <= 1008016$.\n\nWords 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).\n\nWords 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.\n\nWhen $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).\n\nThe output should consist of a single line, whose content is an integer, the total number of distinct word grids.\n\n*Sample Explanation 1*\n\nThe solutions are:  \n\n*Sample Explanation 2*\n\nThe solutions are:  \n\n"},{"iden":"input","content":"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)."},{"iden":"output","content":"The output should consist of a single line, whose content is an integer, the total number of distinct word grids."},{"iden":"examples","content":"Input3 4\n4 5\nwar\nare\nyes\nsat\nsays\narea\ntest\nways\nrest\nOutput2\nInput3 7\n3 7\nran\nage\nnow\nits\nthe\nset\nago\nran\nage\nnow\nits\nthe\nset\nago\nOutput2\n"},{"iden":"note","content":"*Sample Explanation 1*The solutions are:  *Sample Explanation 2*The solutions are:  "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N, M \\in \\mathbb{Z} $ be the number of rows and columns of the grid, respectively.  \nLet $ V = \\{v_1, v_2, \\dots, v_A\\} $ be a set of $ A $ distinct $ N $-letter words (vertical words).  \nLet $ H = \\{h_1, h_2, \\dots, h_B\\} $ be a set of $ B $ distinct $ M $-letter words (horizontal words).  \n\n**Constraints**  \n1. $ 2 \\leq N, M \\leq 4 $  \n2. $ 1 \\leq A \\cdot B \\leq 1008016 $  \n3. All words consist of lowercase English letters.  \n4. If $ N = M $, then $ V \\cap H = \\emptyset $ for cross-use:  \n   - Words in $ V $ cannot be used horizontally unless $ v \\in H $,  \n   - Words in $ H $ cannot be used vertically unless $ h \\in V $.  \n\n**Objective**  \nCount the number of $ N \\times M $ grids such that:  \n- Each row $ i \\in \\{1, \\dots, N\\} $ is assigned a word $ h_{j_i} \\in H $ (horizontal),  \n- Each column $ j \\in \\{1, \\dots, M\\} $ is assigned a word $ v_{k_j} \\in V $ (vertical),  \n- For all $ i \\in \\{1, \\dots, N\\}, j \\in \\{1, \\dots, M\\} $, the character at position $ (i,j) $ matches:  \n  $$\n  v_{k_j}[i] = h_{j_i}[j]\n  $$\n\nThat is, the grid is consistent with both row and column word assignments.  \n\nThe total number of such consistent grids is:  \n$$\n\\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|\n$$","simple_statement":"Given an N×M grid, you can place N vertical words (each of length M) from list A and M horizontal words (each of length N) from list B. Count how many valid grids can be formed such that every cell matches both its vertical and horizontal word.","has_page_source":false}