Flipping Out

Time limit2sMemory limit512 MB

Summary

Count the strings that, added to the given patterns, make the flip rule reproduce the given flip sequence, or -1 if infinitely many work.

Level: Hard8 of 10
Topics: String, Dynamic programming, String matching, Combinatorics
Solved: No attempts yet

Problem

Here is a way to generate coin flips that looks random but is not. First, fix a few patterns, each a string of heads H and tails T. To produce each new flip, scan every flip produced so far and count how many times each pattern occurs in them. Add all of those counts. If the sum is even, the next flip is T. If the sum is odd, the next flip is H.

Take these three patterns:

HTH
THH
T

They generate the sequence THHTHTHT...

T, because at the start no pattern occurs at all, and 0 is even.
H, because the pattern T occurs once, for a sum of 1.
H, because the pattern T still occurs only once, for a sum of 1.
T, because there is one T and one THH, 2 in total.
H, because there are two Ts and one THH, 3 in total.
T, because there are two Ts, one THH and one HTH, 4 in total.
H, because there are three Ts, one THH and one HTH, 5 in total.
T, because there are three Ts, one THH and two HTHs, 6 in total. Overlapping occurrences of HTH are all counted.

Now suppose one pattern went missing from the set. Given the remaining patterns and a string of flips, count the candidates for the missing pattern. A candidate is a nonempty string of H and T such that putting it back with the given patterns and applying the rule above reproduces the given string of flips from the very first flip. The missing pattern cannot be equal to any of the given patterns.

Input

The input consists of a single test case. The first line contains an integer $n$ , the number of patterns ( $1 \le n \le 100{,}000$ ).

Each of the next $n$ lines contains one string made only of the capital letters T and H. The first $n-1$ strings are the patterns, and the last one is the string of flips generated by the rule above.

The sum of the lengths of the $n$ strings is at most $10^6$ . All strings are distinct and none of them is empty.

Output

Print the number of candidates for the missing pattern on one line. Print -1 if there are infinitely many candidates.

Examples4

Example 1
Input
```
2
H
HTTTT
```
Expected output
```
0
```
Example 2
Input
```
1
THHHHH
```
Expected output
```
1
```
Example 3
Input
```
5
H
TTH
HHTHT
TH
TTTHTT
```
Expected output
```
1
```
Example 4
Input
```
5
TTH
H
T
HT
THTTHTTH
```
Expected output
```
2
```