Swap

#include <bits/stdc++.h>
using namespace std;
 
const int LETTERS = 3;
const int MAX_SWAPS = 435;  // ver la pista de arriba
 
int main() {
	string s;
	cin >> s;
	int k;
	cin >> k;
 
	int n = (int)s.size();
	vector<int> count(LETTERS);
	for (char &x : s) {
		if (x == 'K') {
			count[0]++;
		} else if (x == 'E') {
			count[1]++;
		} else {
			count[2]++;
		}
	}
 
	// guarda la cantidad de ocurrencias de una letra en un prefijo
	vector<vector<int>> pref(n + 1, vector<int>(LETTERS));
	// guarda la posición de la i-ésima letra
	vector<vector<int>> pos(LETTERS);
 
	for (int i = 0; i < n; i++) {
		pref[i][0] = (i - 1 >= 0 ? pref[i - 1][0] : 0) + (s[i] == 'K');
		pref[i][1] = (i - 1 >= 0 ? pref[i - 1][1] : 0) + (s[i] == 'E');
		pref[i][2] = (i - 1 >= 0 ? pref[i - 1][2] : 0) + (s[i] == 'Y');
 
		if (s[i] == 'K') {
			pos[0].push_back(i);
		} else if (s[i] == 'E') {
			pos[1].push_back(i);
		} else {
			pos[2].push_back(i);
		}
	}
 
	vector<vector<vector<vector<long long>>>> dp(
	    MAX_SWAPS,
	    vector<vector<vector<long long>>>(
	        count[0] + 1, vector<vector<long long>>(
	                          count[1] + 1, vector<long long>(count[2] + 1, 0))));
 
	// caso base (una forma de crear una cadena vacía)
	dp[0][0][0][0] = 1;
	long long ans = 0;
	for (int ks = 0; ks <= count[0]; ks++) {
		for (int es = 0; es <= count[1]; es++) {
			for (int ys = 0; ys <= count[2]; ys++) {
				for (int cur = 0; cur < MAX_SWAPS; cur++) {
					// desplazamos la siguiente 'K' a la cadena
					if (ks < count[0]) {
						// intercambiamos las letras que están en el camino
						int cost = max(0, pref[pos[0][ks]][1] - es) +
						           max(0, pref[pos[0][ks]][2] - ys);
 
						if (cur + cost < MAX_SWAPS) {
							dp[cur + cost][ks + 1][es][ys] += dp[cur][ks][es][ys];
						}
					}
 
					// desplazamos la siguiente 'E' a la cadena
					if (es < count[1]) {
						int next = pos[1][es];
						// intercambiamos las letras que están en el camino
						int cost =
						    max(0, pref[next][0] - ks) + max(0, pref[next][2] - ys);
 
						if (cur + cost < MAX_SWAPS) {
							dp[cur + cost][ks][es + 1][ys] += dp[cur][ks][es][ys];
						}
					}
 
					// desplazamos la siguiente 'Y' a la cadena
					if (ys < count[2]) {
						int next = pos[2][ys];
						// intercambiamos las letras que están en el camino
						int cost =
						    max(0, pref[next][0] - ks) + max(0, pref[next][1] - es);
 
						if (cur + cost < MAX_SWAPS) {
							dp[cur + cost][ks][es][ys + 1] += dp[cur][ks][es][ys];
						}
					}
 
					// se usaron todas las letras + no excedemos los intercambios
					if (ks == count[0] && es == count[1] && ys == count[2] &&
					    cur <= k) {
						ans += dp[cur][ks][es][ys];
					}
				}
			}
		}
	}
 
	cout << ans << endl;
}

LETTERS = 3
MAX_SWAPS = 435  # ver la pista de arriba
 
s = input()
k = int(input())
 
n = len(s)
count = [0] * LETTERS
for x in s:
	if x == "K":
		count[0] += 1
	elif x == "E":
		count[1] += 1
	else:
		count[2] += 1
 
# guarda la cantidad de ocurrencias de una letra en un prefijo
pref = [[0] * LETTERS for _ in range(n + 1)]
# guarda la posición de la i-ésima letra
pos = [[] for _ in range(LETTERS)]
 
for i in range(n):
	pref[i][0] = (pref[i - 1][0] if i - 1 >= 0 else 0) + (s[i] == "K")
	pref[i][1] = (pref[i - 1][1] if i - 1 >= 0 else 0) + (s[i] == "E")
	pref[i][2] = (pref[i - 1][2] if i - 1 >= 0 else 0) + (s[i] == "Y")
 
	if s[i] == "K":
		pos[0].append(i)
	elif s[i] == "E":
		pos[1].append(i)
	else:
		pos[2].append(i)
 
dp = [
	[[[0] * (count[2] + 1) for _ in range(count[1] + 1)] for _ in range(count[0] + 1)]
	for _ in range(MAX_SWAPS)
]
 
# caso base (una forma de crear una cadena vacía)
dp[0][0][0][0] = 1
ans = 0
 
for ks in range(count[0] + 1):
	for es in range(count[1] + 1):
		for ys in range(count[2] + 1):
			for cur in range(MAX_SWAPS):
				# desplazamos la siguiente 'K' a la cadena
				if ks < count[0]:
					# intercambiamos las letras que están en el camino
					cost = max(0, pref[pos[0][ks]][1] - es) + max(
						0, pref[pos[0][ks]][2] - ys
					)
					if cur + cost < MAX_SWAPS:
						dp[cur + cost][ks + 1][es][ys] += dp[cur][ks][es][ys]
 
				# desplazamos la siguiente 'E' a la cadena
				if es < count[1]:
					next = pos[1][es]
					# intercambiamos las letras que están en el camino
					cost = max(0, pref[next][0] - ks) + max(0, pref[next][2] - ys)
					if cur + cost < MAX_SWAPS:
						dp[cur + cost][ks][es + 1][ys] += dp[cur][ks][es][ys]
 
				# desplazamos la siguiente 'Y' a la cadena
				if ys < count[2]:
					next = pos[2][ys]
					# intercambiamos las letras que están en el camino
					cost = max(0, pref[next][0] - ks) + max(0, pref[next][1] - es)
					if cur + cost < MAX_SWAPS:
						dp[cur + cost][ks][es][ys + 1] += dp[cur][ks][es][ys]
 
				# se usaron todas las letras y no excedemos los intercambios
				if ks == count[0] and es == count[1] and ys == count[2] and cur <= k:
					ans += dp[cur][ks][es][ys]
 
print(ans)