Description

给定的字符串 $S$ 由 K, E, Y 组成。

在 $S$ 中，至多进行 $K$ 次相邻字符的交换，可以生成多少个不同的字符串。

Format

Input

第一行输入字符串 $S$

第二行输入整数 $K$

Output

输出个数

Samples

KEY
1

3

KKEE
2

4

KKEEYY
1000000000

90

Sample Explain 1

最多交换一次，可以得到三个字符串：key、eky、kye

Sample Explain 2

通过最多两次交换，可以得到四条字符串：kkee、keke、ekke、keek

Limitation

• $2 \leq |S| \leq 30$
• $0 \leq K \leq 10^9$
• $S$ 由 K, E, Y 组成。