Train

Time limit1sMemory limit128 MB

Summary

Sum over all n! orders of the wagon strings the number of occurrences of their concatenation in t.

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

Problem

Little Jacus got a toy train made of $n$ wagons from his mom. On the back of each wagon there is a serial number made of lowercase English letters.

He can line the $n$ wagons up in any order to build a train (always using all $n$ wagons). Reading the wagons' serial numbers from left to right yields a single string $w$ .

He asked his mom to write a string $t$ on a sheet of paper. He treats each string $w$ built from one ordering as a pattern and looks for it in $t$ . Over all $n!$ orderings of the wagons, compute the total number of times the pattern $w$ formed by that ordering occurs in $t$ .

Occurrences at different starting positions are counted separately even when they overlap. The wagons are distinct physical objects, so even if two wagons share the same serial number, each ordering (permutation) is counted on its own.

Input

The first line contains an integer $n$ ( $1 \le n < 10$ ). Each of the next $n$ lines contains the serial number $w_i$ of the $i$ -th wagon; each serial number is a non-empty string of lowercase English letters of length at most $10^5$ . The next line contains the string $t$ , a string of lowercase English letters of length at most $10^6$ .

Output

Print a single integer: the total number of occurrences in $t$ of the patterns formed by all $n!$ orderings of the wagons.

Examples3

Example 1
Input
```
2
ala
ma
alamaalama
```
Expected output
```
3
```
Example 2
Input
```
1
aa
aaaaa
```
Expected output
```
4
```
Example 3
Input
```
2
a
a
aa
```
Expected output
```
2
```