Game of Matchings

Adam and Carol are playing the game of matchings. The board is a string $S = s_1 s_2 \dots s_{|S|}$ of $|S|$ lowercase English letters, and the goal is to find every place where a special kind of pattern $P$ matches inside $S$. The pattern has length $N$ and is given by integers $P_1, P_2, \dots, P_N$ between 1 and 26.

The contiguous substring $s_i s_{i+1} \dots s_{i+N-1}$ starting at position $i$ is a matching of $P$ when some mapping from the numbers of $P$ to lowercase letters meets both conditions: the mapping turns the pattern into $s_i s_{i+1} \dots s_{i+N-1}$, and no two distinct numbers map to the same letter.

For example, if $S$ is awawww and $P$ is $[10, 21, 10]$, the matchings are the two substrings of length three that start at positions 1 and 2, awa and waw. The substring www is not a matching, because the numbers 10 and 21 would both have to map to the letter w.

Adam and Carol lost the answer sheet and are not sure whether they found every matching. Given $S$ and $P$, count the matchings.

The first line contains the string $S$. It is not empty, its length is at most $5 \times 10^5$, and every character is a lowercase letter from a to z.

The second line contains the pattern length $N$ ($1 \le N \le |S|$).

The third line contains the $N$ integers $P_1, P_2, \dots, P_N$ of the pattern, separated by spaces ($1 \le P_i \le 26$).

Print one integer, the number of matchings of $P$ found in $S$.