Splitting Words

Paul is happy today because he has created a simple Dynamic Programming solution that will allow him to split a string without spaces into recognizable words. (Ex. Split "helloworld" into "hello" and "world") This will finally help resolve this! Since Paul wants to share this discovery, he has decided to create a problem on it.


Input Specification


The first line of input contains an integer \(n\). \((30 \le n \le 200)\)

The next \(n\) lines contain an alpha-numeric string, a "word".

The next line contains a string, for your submission to split into words.


Output Specification


Output the number of possible ways the string can be splitted into given words.


Sample Input


6
hello
people
hell
o
peo
ple
hellopeople


Sample Output


4


Sample Explanation


"hellopeople" can be split in four ways:

1. "hello", and "people"

2. "hell", "o", and "people"

3. "hello", "peo", and "ple"

4. "hell", "o", "peo", and "ple"

Comments
  • There are no comments.