코드자몬 암호문 (Large)

코드자몬 괴물은 암호문으로 대화한다. 방식은 다음과 같다.

괴물의 종류마다 고유한 어휘 목록이 있다. 소문자 알파벳으로만 이루어진 서로 다른 단어 $V$개다. 괴물은 말할 때 먼저 자기 어휘에 있는 단어를 늘어놓아 문장을 만든다. 같은 단어가 한 문장에 여러 번 나와도 된다. 그다음 그 문장을 아래 두 단계로 암호문으로 바꾼다.

1. 문장에 있는 각 단어의 글자 순서를 무작위로 섞는다.
2. 공백을 모두 지운다.

괴물의 말을 알아들으면 큰 이득이 되므로 이를 해주는 도구를 만들려고 한다. 첫 단계로 암호문 하나를 받아 그 암호문이 나올 수 있는 원래 문장이 몇 개인지 세려고 한다. 예를 들어 어휘가 "this", "is", "a", "monster", "retsnom"이고 암호문이 "ishtsiarestmon"이면 원래 문장은 다음 네 가지다.

• "is this a monster"
• "is this a retsnom"
• "this is a monster"
• "this is a retsnom"

같은 괴물에게서 얻은 암호문 $S$개가 주어진다. 각 암호문마다 가능한 원래 문장의 개수를 구하라.

답이 매우 커질 수 있으므로 소수 $10^9 + 7$로 나눈 나머지를 출력한다.

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

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

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

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

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