{"raw_statement":[{"iden":"statement","content":"Pheatr has a lot of accounts competing in online programming contests such as contests on TopForces.\n\nSometimes when Pheatr participates in a contest on TopForces but cannot attain a good score directly, he takes advantage of some extra accounts applied for cheating (i. e. sockpuppets) to achieve a higher score: Initially, he builds some wrong codes which can pass the pre-system tests and submits them through the sockpuppets. After that, he uses his main account to challenge these sockpuppets immediately, since a successful challenge provides him $100$ more score points.\n\nActually, Pheatr is not the only one who cheats in the contests. Many competitors use the same strategy during online programming contests. It is well known that everyone has only one account as the main account. If one's cheating is revealed, the main account of the one will be banned forever. To prevent the notorious fact from being exposed, each competitor would not register more than two sockpuppets. In spite of great peril, when they register their sockpuppets, these competitors always follow the same rule that the username of a sockpuppet belonging to one competitor should be a prefix of that of the competitor's main account, otherwise the username of the main account should be a prefix of that of the sockpuppet.\n\nRecently, a leak from TopForces provided a list of verified cheaters who have used sockpuppets for cheating, containing the usernames of their main accounts. Besides, TopForces also published a list of suspicious accounts, implying some of them may be sockpuppets. In order to differentiate these suspicious accounts and point out their owners, Pheatr intends to describe all the possibilities according to the published information. Certainly, one should notice that some of the suspicious accounts may be wronged and do not belong to any known cheaters.\n\nAfter recognizing your outstanding programming skills, Pheatr asks you to count the number of distinct possibilities in total for claiming the affiliations between verified cheaters and suspicious accounts. Two possibilities are considered the same if each suspicious account is wronged simultaneously or belongs to the same competitor in both possibilities. Since the answer can be pretty large, you are only asked to report the answer modulo $(10^9 + 7)$.\n\nThe input contains several test cases, and the first line contains a positive integer $T$ indicating the number of test cases which is up to $100$.\n\nFor each test case, the first line contains two integers $n$ and $m$ indicating the number of known cheaters in the leak and the number of suspicious accounts provided by TopForces respectively, where $1 <= n, m <= 1000$.\n\nEach of the following $n$ lines contains a non-empty string $s$ in all lowercase letters representing the username of the main account for a known cheater, where the length of $s$ is up to $10$.\n\nAnd each of the following $m$ lines contains a non-empty string $t$ in all lowercase letters representing the username of a suspicious account, where the length of $t$ is up to $10$.\n\nWe guarantee that all usernames appeared in the same test case are distinct.\n\nFor each test case, output a line containing \"_Case #x: y_\" (without quotes), where _x_ is the test case number starting from $1$, and _y_ is the answer modulo $(10^9 + 7)$ to this test case.\n\nIn the first sample case, both sockpuppets _aa_ and _aaa_ can belong to the owner of _a_.\n\nIn the second sample case, the sockpuppet _ab_ cannot belong to the owner of _aa_, while _a_ can.\n\nIn the third sample case, each sockpuppet can belong to anyone in the list leaked from TopForces.\n\n"},{"iden":"input","content":"The input contains several test cases, and the first line contains a positive integer $T$ indicating the number of test cases which is up to $100$.For each test case, the first line contains two integers $n$ and $m$ indicating the number of known cheaters in the leak and the number of suspicious accounts provided by TopForces respectively, where $1 <= n, m <= 1000$.Each of the following $n$ lines contains a non-empty string $s$ in all lowercase letters representing the username of the main account for a known cheater, where the length of $s$ is up to $10$.And each of the following $m$ lines contains a non-empty string $t$ in all lowercase letters representing the username of a suspicious account, where the length of $t$ is up to $10$.We guarantee that all usernames appeared in the same test case are distinct."},{"iden":"output","content":"For each test case, output a line containing \"_Case #x: y_\" (without quotes), where _x_ is the test case number starting from $1$, and _y_ is the answer modulo $(10^9 + 7)$ to this test case."},{"iden":"note","content":"In the first sample case, both sockpuppets _aa_ and _aaa_ can belong to the owner of _a_.In the second sample case, the sockpuppet _ab_ cannot belong to the owner of _aa_, while _a_ can.In the third sample case, each sockpuppet can belong to anyone in the list leaked from TopForces."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ D \\in \\{ \\text{'o'}, \\text{':'} \\}^{3 \\times 3} $ be a $3 \\times 3$ grid representing the top face of a die, where 'o' denotes a dent and ':' denotes a smooth surface.\n\nLet $ \\mathcal{S} = \\{ S_1, S_2, S_3, S_4, S_5, S_6 \\} $ be the set of valid die face patterns, each represented as a $3 \\times 3$ grid, where:\n\n- $ S_1 = \\begin{bmatrix} \\text{:} & \\text{:} & \\text{:} \\\\ \\text{:} & \\text{o} & \\text{:} \\\\ \\text{:} & \\text{:} & \\text{:} \\end{bmatrix} $\n- $ S_2 = \\begin{bmatrix} \\text{o} & \\text{:} & \\text{:} \\\\ \\text{:} & \\text{:} & \\text{:} \\\\ \\text{:} & \\text{:} & \\text{o} \\end{bmatrix} $\n- $ S_3 = \\begin{bmatrix} \\text{o} & \\text{:} & \\text{:} \\\\ \\text{:} & \\text{o} & \\text{:} \\\\ \\text{:} & \\text{:} & \\text{o} \\end{bmatrix} $\n- $ S_4 = \\begin{bmatrix} \\text{o} & \\text{:} & \\text{o} \\\\ \\text{:} & \\text{:} & \\text{:} \\\\ \\text{o} & \\text{:} & \\text{o} \\end{bmatrix} $\n- $ S_5 = \\begin{bmatrix} \\text{o} & \\text{:} & \\text{o} \\\\ \\text{:} & \\text{o} & \\text{:} \\\\ \\text{o} & \\text{:} & \\text{o} \\end{bmatrix} $\n- $ S_6 = \\begin{bmatrix} \\text{o} & \\text{:} & \\text{o} \\\\ \\text{o} & \\text{:} & \\text{o} \\\\ \\text{o} & \\text{:} & \\text{o} \\end{bmatrix} $\n\nLet $ R(D) $ denote the set of all 4 rotations of $ D $ (0°, 90°, 180°, 270°).\n\n**Constraints**  \n$ D $ is given as 3 lines of 3 characters each, each character in $ \\{ \\text{'o'}, \\text{':'} \\} $.\n\n**Objective**  \nDetermine $ v \\in \\{1, 2, 3, 4, 5, 6\\} $ such that $ D \\in R(S_v) $.  \nIf no such $ v $ exists, output \"unknown\".","simple_statement":"Given a 3x3 grid of 'o' and ':', determine the number on a die face (1 to 6) or output \"unknown\" if it's not a valid die face.","has_page_source":false}