Abbreviated Substring Count

In the programming community, a novel abbreviation method has become popular. For any string S with length L, its abbreviation is formed by keeping only the first and last characters and replacing the intermediate characters with the count of those characters. Formally, if L \ge K, the abbreviation of S is:

\( S[0] \; + \; (L-2) \; + \; S[L-1] \)

For example, internationalization is abbreviated as i18n and Lanqiao as L5o.

Given a string S and two characters c₁ and c₂, count the number of substrings of S that start with c₁ and end with c₂ which can be abbreviated using this method (i.e. the substring's length is at least K).

inputFormat

The input consists of three lines:

1. A non-empty string S consisting of only English letters.
2. An integer K representing the minimum length required for a substring to be abbreviated.
3. Two space-separated characters c1 and c2.

You can assume that K is positive and that the characters c1 and c2 appear in S at least once.

outputFormat

Output a single integer representing the number of substrings of S that start with c1 and end with c2 and have a length of at least K.

sample

abcaab
2
a b

4