Codejamon 암호

Codejamon 괴물들은 암호화된 메시지로 대화한다. 그 방식은 다음과 같다:

괴물의 각 종류에는 저마다 고유한 어휘가 있다. 이는 소문자 영어 알파벳으로만 이루어진 V개의 서로 다른 단어 목록이다. 괴물이 말을 할 때는 먼저 자신의 어휘에 있는 단어들로 문장을 만든다. 같은 단어가 한 문장에 여러 번 나타날 수도 있다. 그런 다음, 다음과 같이 문장을 암호화된 문자열로 바꾼다:

• 문장에 있는 각 단어의 글자 순서를 무작위로 섞는다.

• 모든 공백을 제거한다.

괴물들의 말을 이해하면 엄청난 이점을 얻을 수 있으므로, 이를 위한 도구를 만들고 있다. 첫 단계로, 암호화된 문자열을 받아 그 문자열을 만들어 낼 수 있는 원래 문장이 몇 가지인지 알아내고자 한다. 예를 들어, 어떤 괴물의 어휘가 ["this", "is", "a", "monster", "retsnom"]이고 암호화된 문자열 "ishtsiarestmon"을 말한다면, 가능한 원래 문장은 네 가지이다:

• "이것은 괴물이다"

• "이것은 물괴이다"

• "괴물은 이것이다"

• "물괴는 이것이다"

같은 괴물에게서 얻은 S개의 암호화된 문자열이 있다. 각 문자열에 대해 가능한 원래 문장의 수를 알아낼 수 있는가?

IMPORTANT: Since 출력값은 매우 큰 수가 될 수 있으므로, 결과를 소수 $10^{9}$ + 7 (1000000007)로 나눈 나머지만 출력하면 된다.

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB. 1 ≤ S ≤ 5.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ 괴물의 어휘에 있는 각 단어의 길이 ≤ 5. 1 ≤ 암호화된 문자열의 길이 ≤ 50. 5 ≤ V ≤ 10.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ 괴물의 어휘에 있는 각 단어의 길이 ≤ 20. 2000 ≤ 암호화된 문자열의 길이 ≤ 4000. 200 ≤ V ≤ 400.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어지며, 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 정수 V와 S가 있는 한 줄로 시작하며, 각각 괴물의 어휘 크기와 암호화된 문자열의 수를 나타낸다. 그다음 V개의 줄이 주어진다. 각 줄에는 소문자 영어 알파벳으로 이루어진 문자열 하나가 있으며, 괴물의 어휘에 있는 단어를 나타낸다. 마지막으로 S개의 줄이 주어진다. 각 줄에는 소문자 영어 알파벳으로만 이루어진 문자열이 있으며, 암호화된 문장을 나타낸다. 모든 암호화된 문장은 유효함이 보장된다. 즉, 각 문장에는 가능한 원래 문장이 적어도 하나 있다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이며(1부터 시작), y은 S개의 정수를 공백으로 구분한 목록이다. 이 정수들은 문제 설명에 나온 대로 입력에 주어진 순서에 따른 각 암호화된 문장의 답을 각각 $10^{9}$ + 7로 나눈 나머지이다.