Xiao Dou is participating in a biology experiment. In the laboratory, he is mainly studying proteins. The protein he is currently studying is composed of $k$ amino acids in a specific order. Each amino acid can be represented by a sequence of $a$ bases, denoted as $s_{i,j}$. Now, Xiao Dou has a base sequence $s$, and he wants to know how many different combinations of amino acids can form this protein. Specifically, he wants to find the number of different ways to concatenate $k$ segments of amino acid sequences to match the sequence $s$. Two ways are considered different if the selection of the $k$ segments is different, or if the positions where they match $s$ are different.

Input

The first line contains an integer, representing the number of amino acids $k$ in the protein. The second line contains a string $s$, representing the existing base sequence. Starting from the third line, the next $k$ lines represent the possible base sequences for each amino acid. For the $i$-th amino acid, $a_i$ represents the number of possible base sequences for this amino acid, followed by $a_i$ strings representing the possible base sequences, separated by spaces.

Output

Output a single integer representing the number of different schemes (a scheme is defined by different base sequences or different amino acid sequences for the same base sequence).

Examples

Input 1

2
ABC
2 A AB
2 C BC

Output 1

2

Note 1

• Choosing A for the first and C for the second results in AC, which matches ABC with 0 matches.
• Choosing A for the first and BC for the second results in ABC, which matches ABC with 1 match.
• Choosing AB for the first and C for the second results in ABC, which matches ABC with 1 match.
• Choosing AB for the first and BC for the second results in ABBC, which matches ABC with 0 matches. Therefore, there are 2 ways in total.

Input 2

2
AAA
2 A AA
2 A AA

Output 2

4

Note 2

• Choosing A for the first and A for the second results in AA, which matches AAA with 2 matches.
• Choosing A for the first and AA for the second results in AAA, which matches AAA with 1 match.
• Choosing AA for the first and A for the second results in AAA, which matches AAA with 1 match.
• Choosing AA for the first and AA for the second results in AAAA, which matches AAA with 0 matches. Therefore, there are 4 ways in total.

Constraints

For 30% of the data, $1 \le k \le 25$, $|s| \le 10000, a_i \le 3$. For 100% of the data, $1 \le k \le 100$, $|s| \le 10000, a_i \le 10$.