Home

Contest: Task: Related: TaskD TaskF

Score : $500$ points

Problem Statement

Given is a string $S$ consisting of K, E, Y.

How many strings are there that can be obtained with at most $K$ swaps of two adjacent characters in $S$?

Constraints

  • $2 \leq |S| \leq 30$
  • $0 \leq K \leq 10^9$
  • $S$ consists of K, E, Y.

Input

Input is given from Standard Input in the following format:

$S$
$K$

Output

Print the answer.

Sample Input 1

KEY
1

Sample Output 1

3

With at most one swap, there are three strings that can be obtained: KEY, EKY, KYE.

Sample Input 2

KKEE
2

Sample Output 2

4

With at most two swaps, there are four strings that can be obtained: KKEE, KEKE, EKKE, KEEK.

Sample Input 3

KKEEYY
1000000000

Sample Output 3

90