405416: GYM101955 A Sockpuppets

Pheatr has a lot of accounts competing in online programming contests such as contests on TopForces.

Sometimes 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.

Actually, 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.

Recently, 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.

After 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)$$$.

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 \le n, m \le 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.

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.

3
1 2
a
aa
aaa
1 2
aa
a
ab
5 5
a
ah
ahd
ahdo
ahdoc
ahdoca
ahdocah
ahdocahd
ahdocahdo
ahdocahdoc

Case #1: 4
Case #2: 2
Case #3: 6396

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.