A37500.又是字符串

Yuilice有一个只包含$K,E,Y$三种字符的字符串，现在可以进行$0 \sim k$次以下操作：交换两个相邻位置上的字符。

Yuilice 想知道：能生成多少种不同的字符串？

第一行输入一个字符串$s$。

第二行一个整数$k$。

输出一个正整数表示答案。

【样例1解释】

可以生成KEY,EKY,KYE3个不同的字符串。

【样例2解释】

可以生成KKEE, KEKE, EKKE, KEEK4个不同的字符串

数据规模与约定

对于测试点$1\sim 4$，保证字符串长度$\leq 10$。

对于测试点$5\sim10$，保证字符串长度$\leq 15$。

对于测试点$11 \sim 20$，保证字符串长度$\leq 30$。

对于所有测试点，保证$k$在$int$范围内。