Dangerous Pattern

Time Limit: 2 Seconds
Memory Limit: 32768 KB

The FBI has just now got the information that the terrorists are machinating
a new terroristic attack. The terrorists keep contact in some magazines, newspapers,
in some crypto ways. We will say a section of text contains dangerous pattern
if S[1], S[2], ..., S[K] (S[1], S[2], ... S[K] is given to you) appears in the
specified order and does not overlap.

For example if we have

K = 2

S[1] = 'aa'

S[2] = 'ab'

the text 'aaab' contains a dangerous pattern but the text 'aab' does not. Because
the appearance of 'aa' (position [1, 2]) and the appearance of 'ab' (position
[2, 3]) overlaps. Neither does 'abaa' because the appearance of them ([3, 4]
and [1, 2]) are not in the specified order.

Now it turns to you the task to count how many different dangerous patterns
a given text contains. We will say that two dangerous patterns are different
when and only when there is at least S[i] such that the appearance of S[i] in
this two patterns differs.

For example, if

K = 2

S[1] = 'a'

S[2] = 'b'

text = 'aabb'

There are four different dangerous patterns in this text ([1, 3], [1, 4], [2,
3], [2, 4] represented by the position of the appearance.

The result may be too large, you need only to output the remainder that the
result divides 28851.

Some constraints for this problem:

1. The total length of the S[i] does not exceed 10,000.

2. For all the string S[1], S[2], ..., S[K], there are no two string S[i] and
S[j] such that S[i] is the suffix of S[j].

3. The total length of the text does not exceed 500,000.

4. The character that appears in S[i] or in the text are all latin letters in
lowercases. (i.e. 'a' .. 'z')

**Input**

The first line of the input is a single number X (0 < X <= 10), the number
of the test cases of the input. Then X blocks each represents a single test
case.

For each block the first line is an integer K. Then K lines, the (i+1)-th lines
represents S[i]. Then one line whose length does not exceed 500,000 represents
the text.

There're NO breakline between two continuous test cases.

**Output**

For each block output one line that is the remainder that the number of different
dangerous patterns divides 28851.

**Sample Input**

2

2

a

b

aabb

2

a

b

aabb

**Sample Output**

4

4

*
(adviser)*

**Site:** *http://zhuzeyuan.hp.infoseek.co.jp/index.files/our_contest_20040619.htm*

Author:

**XIN, Tao**
Source:

**Online Contest of Christopher's Adventure**
Submit
Status