Problem Description

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.

Input Format

The first line contains an integer $K$.

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

Output Format

Output one integer representing the answer.

4
abababdb a b

6

Hint

[Sample Explanation]

The substrings that meet the conditions are as follows, where the substring is inside the square brackets:

[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