当前没有测试数据。

E - 交换

得分：$500$ 分

问题描述

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

在进行最多 $K$ 次相邻字符交换的情况下，能够得到多少个不同的字符串？

约束条件

• $2 \leq |S| \leq 30$
• $0 \leq K \leq 10^9$
• $S$ 由字符 K、E、Y 构成。

输入

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

$S$

$K$

输出

输出答案。

KEY
1

3

在最多交换一次的情况下，能够得到三个不同的字符串： KEY、 EKY、 KYE。

KKEE
2

4

在最多交换两次的情况下，能够得到四个不同的字符串： KKEE、 KEKE、 EKKE、 KEEK。

KKEEYY
1000000000

90

在最多交换 $10^9$ 次的情况下，能够得到 $90$ 个不同的字符串。