Protein Combination Matching

A protein is composed of k amino acids in a fixed order. For the i-th amino acid (1 ≤ i ≤ k), there are a possible candidate base sequences, denoted by \(s_{i,1}, s_{i,2}, \dots, s_{i,a}\). You are also given a DNA string \(s\). A combination way is defined as follows:

• For each amino acid from 1 to \(k\), choose one of its candidate sequences.
• Let \(p = s_{1,j_1} s_{2,j_2} \cdots s_{k,j_k}\) be the concatenation of the chosen candidate sequences.
• Find an occurrence of \(p\) as a contiguous substring of \(s\). (If \(p\) appears multiple times at different positions in \(s\), each occurrence is counted separately.)

Two ways are considered different if either the selection of candidate sequences differs or the occurrence (i.e. the matching starting position in \(s\)) differs. Your task is to compute the total number of different ways.

inputFormat

The input consists of several lines:

1. The first line contains two integers \(k\) and \(a\) (1 ≤ k, a ≤ 10), where \(k\) is the number of amino acids in the protein, and \(a\) is the number of candidate base sequences for each amino acid.
2. The next \(k\) lines each contain \(a\) nonempty strings (each consisting of uppercase letters A, C, G, T) separated by spaces. The \(i\)-th of these lines represents the \(a\) candidate sequences for the \(i\)-th amino acid.
3. The last line contains a nonempty string \(s\) (consisting of uppercase letters A, C, G, T) representing the DNA sequence.

outputFormat

Output a single integer — the total number of different ways to obtain a protein from the DNA string \(s\) by the process described.

sample

2 2
AT GC
TA CG
ATCGTAATTA

2