P9244 [Lanqiao Cup 2023 NOI Qualifier B] Substring Abbreviation

A very new abbreviation method is becoming popular among programmers: for a string, keep only the first and last characters, and replace all characters between them with the length of that middle part. For example, `internationalization` is abbreviated as `i18n`, `Kubernetes` (note that the hyphen is not part of the string) is abbreviated as `K8s`, and `Lanqiao` is abbreviated as `L5o`, etc. In this problem, we规定 that any string with length greater than or equal to $K$ can use this abbreviation method (strings with length less than $K$ do not qualify to use this abbreviation). Given a string $S$ and two characters $c_{1}$ and $c_{2}$, please compute how many substrings of $S$ that start with $c_{1}$ and end with $c_{2}$ can use this abbreviation method.

The first line contains an integer $K$. The second line contains a string $S$ and two characters $c_{1}$ and $c_{2}$.

Output one integer representing the answer.

**[Sample Explanation]** The substrings that meet the conditions are as follows, where the substring is inside the square brackets: ```plain [abab]abdb [ababab]db [abababdb] ab[abab]db ab[ababdb] abab[abdb] ``` **[Constraints and Conventions for Test Cases]** For $20\%$ of the testdata, $2 \leq K \leq |S| \leq 10^4$. For $100\%$ of the testdata, $2 \leq K \leq |S| \leq 5 \times 10^{5}$. $S$ contains only lowercase letters. Both $c_{1}$ and $c_{2}$ are lowercase letters. $|S|$ denotes the length of the string $S$. Lanqiao Cup 2023 Provincial Contest B Group Problem G. Translated by ChatGPT 5