题目描述

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

在最多进行 $K$ 次两个相邻字符交换的情况下，有多少个字符串可以从 $S$ 获得？

约束条件

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

输入

输入以以下格式从标准输入给出：

$S$ $K$

输出

输出答案。

示例输入 1

KEY
1

示例输出 1

3

最多进行一次交换，可以得到三个字符串：KEY、EKY、KYE。

示例输入 2

KKEE
2

示例输出 2

4

最多进行两次交换，可以得到四个字符串：KKEE、KEKE、EKKE、KEEK。

示例输入 3

KKEEYY
1000000000

示例输出 3

90