오타

Gunilla는 자신이 가장 좋아하는 웹사이트에 접속하려고 한다. 하지만 가끔 특정 글자들을 혼동하여 대신 다른 웹사이트에 접속하게 된다. 흥미롭게도 그녀는 같은 주소에서 정확히 같은 실수를 두 번 하는 일은 없다.

그녀가 가장 좋아하는 웹사이트의 주소와 그녀가 흔히 혼동하는 글자들에 대한 설명이 주어질 때, 해커들이 그녀를 자신들의 웹사이트로 유인하기 위해 등록해야 하는 주소 목록의 길이를 출력한다.

채점

세 테스트 케이스 그룹으로 해답을 테스트한다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

1 | 30 | 답은 200보다 작고, $N$개의 모든 혼동 문자열에는 정확히 2개의 글자가 있다

2 | 30 | 답은 10000보다 작다

3 | 40 | 답은 2십억보다 작다

첫째 줄에 문자열 하나, 즉 Gunilla가 가장 좋아하는 웹사이트의 주소가 주어진다. a-z의 글자와 마침표만 등장하며, 길이는 2자 이상 20자 이하이다. 실제 주소일 필요도, 올바른 구조를 갖춘 주소일 필요도 없다. 둘째 줄에는 Gunilla가 혼동하는 글자 그룹의 수인 정수 $N$가 주어진다. (여기서 $1 \le N \le 13$). 이어지는 $N$개의 각 줄에는 2개 이상 26개 이하의 글자로 이루어진 문자열이 하나씩 주어진다. 문자열의 모든 글자는 서로 다르며 a-z에서 선택된다. 각 문자열의 글자들은 모든 글자가 서로 혼동될 수 있는 하나의 그룹을 이룬다. 예를 들어 문자열이 "boi"이면, "b"을 "o" 또는 "i"으로 바꿀 수 있고, "o"를 "b" 또는 "i"으로 바꿀 수 있으며, "i"을 "b" 또는 "o"로 바꿀 수 있다는 뜻이다. 어떤 글자도 둘 이상의 그룹에 등장하지 않는다.

Gunilla가 적어도 한 번 오타를 내되 정확히 같은 오타(특정 글자를 특정한 다른 글자로 바꾸는 것)를 여러 번 내지 않음으로써 접속할 수 있는 주소의 수를 정수로 출력한다.

처음 세 예제에서 가능한 해커 주소는 다음과 같다.

po.pe     kartis.com      abbe
so.pe     katris.com      abbi
so.se     kartix.com      ebba
          katrix.com      ebbi
          kattix.com      ibba
          kartiz.com      ibbe
          katriz.com
          kattiz.com

같은 실수를 두 번 한 "karris.com" 및 "ebbe" 같은 주소가 없다는 점에 유의한다.