사라진 동전 패턴

동전 던지기 결과를 무작위처럼 보이게 만들지만 실제로는 전혀 무작위가 아닌 방법이 있다. 먼저 앞면 H와 뒷면 T로 이루어진 문자열 몇 개를 패턴으로 정한다. 새로운 동전 던지기 결과를 하나 만들 때마다 지금까지 나온 결과 전체를 앞에서부터 살펴보면서 각 패턴이 몇 번 등장하는지 센다. 그 횟수를 모두 더한 값이 짝수면 다음 결과는 T이고, 홀수면 H이다.

패턴이 다음 세 개라고 하자.

HTH
THH
T

이 세 패턴은 THHTHTHT...라는 결과를 만든다.

1. 처음에는 어떤 패턴도 등장하지 않아 합이 0이고, 0은 짝수이므로 T이다.
2. 패턴 T가 한 번 등장해 합이 1이므로 H이다.
3. 아직도 패턴 T가 한 번뿐이라 합이 1이므로 H이다.
4. T가 하나, THH가 하나로 합이 2이므로 T이다.
5. T가 둘, THH가 하나로 합이 3이므로 H이다.
6. T가 둘, THH가 하나, HTH가 하나로 합이 4이므로 T이다.
7. T가 셋, THH가 하나, HTH가 하나로 합이 5이므로 H이다.
8. T가 셋, THH가 하나, HTH가 둘로 합이 6이므로 T이다. HTH가 서로 겹쳐서 등장해도 겹친 만큼 모두 센다.

이제 패턴 하나가 집합에서 빠졌다고 하자. 남은 패턴과 결과 문자열이 주어질 때, 빠진 패턴의 후보가 몇 개인지 구하라. 후보는 H와 T로 이루어진 비어 있지 않은 문자열 중에서, 남은 패턴에 그 문자열을 다시 넣고 위 규칙을 적용했을 때 처음부터 주어진 결과 문자열과 똑같은 결과가 나오는 것을 말한다. 빠진 패턴은 주어진 패턴 중 어느 것과도 같을 수 없다.

입력은 테스트 케이스 하나로 이루어진다. 첫 줄에 패턴의 개수를 나타내는 정수 $n$이 주어진다 ($1 \le n \le 100{,}000$).

다음 $n$개의 줄에는 대문자 T와 H로만 이루어진 문자열이 한 줄에 하나씩 주어진다. 이 중 처음 $n-1$개는 패턴이고, 마지막 하나는 위 규칙으로 만들어진 결과 문자열이다.

$n$개 문자열의 길이 합은 $10^6$ 이하이다. 모든 문자열은 서로 다르고, 빈 문자열은 없다.

빠진 패턴의 후보 개수를 한 줄에 출력한다. 후보가 무한히 많으면 -1을 출력한다.