코드자몬 암호문 (작은 입력)

코드자몬 몬스터는 암호문으로 말한다. 몬스터 종류마다 고유한 어휘가 있고, 어휘는 영어 소문자로만 이루어진 서로 다른 단어 $V$개의 목록이다.

몬스터는 말을 할 때 먼저 자기 어휘에 있는 단어로 문장을 만든다. 한 문장에 같은 단어가 여러 번 나와도 된다. 그다음 두 단계로 문장을 암호문으로 바꾼다.

1. 각 단어의 글자를 무작위로 섞는다.
2. 공백을 모두 없앤다.

암호문 하나가 주어지면 그 암호문이 나올 수 있는 원래 문장이 몇 가지인지 세려고 한다. 단어의 나열이 다르면 다른 문장이고, 글자를 섞으면 서로 같아지는 두 단어도 각각 다른 단어로 센다. 예를 들어 어휘가 ["this", "is", "a", "dog", "god"]이고 암호문이 ishtsiaogd이면 원래 문장은 네 가지다.

• is this a dog
• is this a god
• this is a dog
• this is a god

같은 몬스터가 만든 암호문 $S$개가 주어진다. 각 암호문마다 가능한 원래 문장의 개수를 구하라. 답이 매우 커질 수 있으므로 소수 $10^9 + 7$로 나눈 나머지를 출력한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 어휘의 크기 $V$와 암호문의 개수 $S$가 공백으로 구분되어 주어진다. 이어지는 $V$개의 줄에는 어휘를 이루는 단어가 한 줄에 하나씩 주어진다. 각 단어는 영어 소문자로만 이루어져 있고 서로 다르다. 그다음 $S$개의 줄에는 암호문이 한 줄에 하나씩 주어지며, 암호문도 영어 소문자로만 이루어져 있다.

모든 암호문은 유효하다. 즉 각 암호문마다 그 암호문을 만들어 내는 원래 문장이 적어도 하나 있다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 입력에 주어진 순서대로 나열한 $S$개의 답을 공백 하나로 구분한 목록이다. 각 답은 $10^9 + 7$로 나눈 나머지다.

• $1 \le T \le 100$
• $5 \le V \le 10$
• $1 \le S \le 5$
• 어휘에 있는 단어의 길이는 1 이상 5 이하이다.
• 암호문의 길이는 1 이상 50 이하이다.