Pattern Matching

Pattern is a nonempty string that may contain lowercase letters of the Latin alphabet and the special character '*' (star).

We will say that a string $T$ matches the pattern $P$ if and only if there is a way to replace the stars in $P$ with (possibly empty) sequences of lowercase letters so that the result equals $T$. For example, the string aadbc matches the pattern a*b*c, as we can obtain the string from the pattern by replacing the first star in the pattern with ad and the second one with the empty string. On the other hand, the string abcbcb does not match this pattern.

Given a non-empty string $S$ consisting of lowercase Latin letters, count the number of cyclic shifts of $S$ that match the given pattern $P$.