問題文

K, E, Y のみからなる文字列 $S$ が与えられます。

$S$ の隣接する $2$ 文字を入れ替える操作を $K$ 回まで行えるとき、作ることができる文字列は何種類ありますか？

制約

• $2 \\leq |S| \\leq 30$
• $0 \\leq K \\leq 10^9$
• $S$ は K, E, Y のみからなる

入力

入力は以下の形式で標準入力から与えられる。

$S$ $K$

出力

答えを出力せよ。

入力例 1

KEY
1

出力例 1

3

KEY に対して $1$ 回以下の操作を行うことで得られる文字列は KEY, EKY, KYE の $3$ 種類です。

入力例 2

KKEE
2

出力例 2

4

KKEE に対して $2$ 回以下の操作を行うことで得られる文字列は KKEE, KEKE, EKKE, KEEK の $4$ 種類です。

入力例 3

KKEEYY
1000000000

出力例 3

90