交换

题目描述

给定一个由 K、E、Y 组成的字符串 $S$。

问:在 $S$ 中最多进行 $K$ 次相邻字符的交换,一共可以得到多少个不同的字符串?

输入格式

输入按以下格式从标准输入给出:

$S$
$K$

输出格式

输出答案。

样例

KEY
1

3

最多交换一次,可以得到三个字符串:KEY、EKY、KYE。

KKEE
2

4

最多交换两次,可以得到四个字符串:KKEE、KEKE、EKKE、KEEK。

KKEEYY
1000000000

90

数据范围

• $2 \le |S| \le 30$
• $0 \le K \le 10^9$
• $S$ 仅由 K、E、Y 组成