Ha

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read()
{
int x;scanf("%d",&x);return x;
}
string s;
char t[100];
vector<int>pos[100];
int k,n,cnt[100],K,sum[31][100];
long long f[31][31][31][910],ans;
int main()
{
cin>>s>>K;
n=s.size();
for(int i=0;i<n;i++)
{
pos[s[i]].push_back(i);//存储出现的下标
cnt[s[i]];//存储出现次数
sum[i+1]['K']=sum[i]['K'];
sum[i+1]['E']=sum[i]['E'];
sum[i+1]['Y']=sum[i]['Y'];
sum[i+1][s[i]];//存储前缀和
}
f[0][0][0][0]=1;
for(int i=0;i<=cnt['K'];i++)
for(int j=0;j<=cnt['E'];j++)
for(int k=0;k<=cnt['Y'];k++)
for(int t=0;t<=900;t++)
{
if(i+1<=cnt['K'])//如果可以向下一状态转移
{
int wei=pos['K'][i];
int cost=max(0,sum[wei]['E']-j)+max(0,sum[wei]['Y']-k);
//计算所需花费
f[i+1][j][k][t+cost]+=f[i][j][k][t];
//更新到下一状态中
}
if(j+1<=cnt['E'])
{
int wei=pos['E'][j];
int cost=max(0,sum[wei]['K']-i)+max(0,sum[wei]['Y']-k);
f[i][j+1][k][t+cost]+=f[i][j][k][t];
}
if(k+1<=cnt['Y'])
{
int wei=pos['Y'][k];
int cost=max(0,sum[wei]['K']-i)+max(0,sum[wei]['E']-j);
f[i][j][k+1][t+cost]+=f[i][j][k][t];
}
if(icnt['K']&&jcnt['E']&&k==cnt['Y']&&t<=K)
ans+=f[i][j][k][t];
//如果本状态是合法状态，累加到答案里
}
cout<<ans;
}