Rhyming Subsequence Selection

Little Mate received an array of lowercase English letters as a gift. He wants to form a word by crossing out some letters (i.e. selecting a subsequence) from the array such that:

• The resulting word has a length of \(D\).
• The last two letters of the word are exactly \(X\) and \(Y\) (i.e. the next-to-last letter is \(X\) and the last letter is \(Y\)).

The task is to determine the number of different ways Mate can cross out letters to satisfy these conditions. Two selections are considered distinct if the sets of positions of the crossed-out letters differ.

inputFormat

The input consists of three lines:

1. A string \(S\) of lowercase English letters.
2. An integer \(D\) representing the desired length of the resulting word.
3. A two-character string representing the required ending letters; the first character is \(X\) (next-to-last) and the second is \(Y\) (last).

outputFormat

Output a single integer: the number of different ways to choose a subsequence from \(S\) such that the resulting word has length \(D\) and ends with the characters \(X\) and \(Y\) in order.

sample

abxy
3
xy

2