Дано рядок \(S\), що складається з K, E, Y.

Скільки існує рядків, які можна отримати за допомогою щонайбільше \(K\) обміну двох сусідніх символів у \(S\)?

Формат вхідних даних

Перший рядок містить рядрк \(S\) (\(2 \le |S| \le 30\))

Другий рядок містить ціле число \(K\) (\(0 \le K \le 10^9\))

Формат вихідних даних

У вихідний потік виведіть шукану кількість.

Примітка

До прикладу 1:

За допомогою щонайбільше одного обміну можна отримати три рядки: KEY, EKY, KYE

Приклад вхідних даних

KEY
1

Приклад вихідних даних

3

Приклад вхідних даних

KKEE
2

Приклад вихідних даних

4

Приклад вхідних даних

KKEEYY
1000000000

Приклад вихідних даних

90