{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003ePheatr has a lot of accounts competing in online programming contests such as contests on TopForces.\u003c/p\u003e\u003cp\u003eSometimes 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.\u0026nbsp;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.\u003c/p\u003e\u003cp\u003eActually, 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\u0027s 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\u0027s main account, otherwise the username of the main account should be a prefix of that of the sockpuppet.\u003c/p\u003e\u003cp\u003eRecently, 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.\u003c/p\u003e\u003cp\u003eAfter 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)$$$.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe 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$$$.\u003c/p\u003e\u003cp\u003eFor 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 \\le n, m \\le 1000$$$.\u003c/p\u003e\u003cp\u003eEach 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$$$.\u003c/p\u003e\u003cp\u003eAnd 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$$$.\u003c/p\u003e\u003cp\u003eWe guarantee that all usernames appeared in the same test case are distinct.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case, output a line containing \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eCase #x: y\u003c/span\u003e\" (without quotes), where \u003cspan class\u003d\"tex-font-style-tt\"\u003ex\u003c/span\u003e is the test case number starting from $$$1$$$, and \u003cspan class\u003d\"tex-font-style-tt\"\u003ey\u003c/span\u003e is the answer modulo $$$(10^9 + 7)$$$ to this test case.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n1 2\na\naa\naaa\n1 2\naa\na\nab\n5 5\na\nah\nahd\nahdo\nahdoc\nahdoca\nahdocah\nahdocahd\nahdocahdo\nahdocahdoc\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 4\nCase #2: 2\nCase #3: 6396\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first sample case, both sockpuppets \u003cspan class\u003d\"tex-font-style-tt\"\u003eaa\u003c/span\u003e and \u003cspan class\u003d\"tex-font-style-tt\"\u003eaaa\u003c/span\u003e can belong to the owner of \u003cspan class\u003d\"tex-font-style-tt\"\u003ea\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eIn the second sample case, the sockpuppet \u003cspan class\u003d\"tex-font-style-tt\"\u003eab\u003c/span\u003e cannot belong to the owner of \u003cspan class\u003d\"tex-font-style-tt\"\u003eaa\u003c/span\u003e, while \u003cspan class\u003d\"tex-font-style-tt\"\u003ea\u003c/span\u003e can.\u003c/p\u003e\u003cp\u003eIn the third sample case, each sockpuppet can belong to anyone in the list leaked from TopForces.\u003c/p\u003e"}}]}