Little Mate got an array of lowercase letters from the English alphabet as a present from his parents. In order to have at least some use of such a clever present, he decided to use it for finding rhymes when writing his next song.
To find a specific rhyme, Mate wants to select a word of length XY
, i.e. where the next to last letter is X
, and the last Y
. Mate's process of selecting a word is by first crossing out some letters in a given sequence, and then merging the letters he didn't cross out into a single word. He wants to know in how many different ways he can cross out the letters so that he meets the given conditions.
The selection of two words is considered distinct if the sets of positions of the crossed-out letters are different.
Input Specification
The first line of input contains an array of lowercase letters of the English alphabet
The second line of input contains the integer
Each of the following XY
from the task.
Output Specification
The
Scoring
In test cases worth
In test cases worth an additional
Sample Input 1
banana
3
2 na
3 ba
4 nn
Sample Output 1
3
0
1
Explanation for Sample Output 1
Word of length 2 that ends with na
can be obtained in the following ways:
b a n a n a, b a n a n a, b a n a n a.
Sample Input 2
malimateodmameitate
3
10 ot
7 aa
3 me
Sample Output 2
2
464
56
Comments