给定一个字符串 $S$ 和一个非负整数 $K$，求从 $S$ 开始至多进行 $K$ 次相邻字符的交换，可以生成多少种不同的字符串。

$2\le |S|\le 30$，$0\le K\le 10^9$，$S$ 只包含字符 K、E、Y。