配点 : $500$ 点

問題文

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

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

制約

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

入力

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

$S$

$K$

出力

答えを出力せよ。

KEY
1

3

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

KKEE
2

4

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

KKEEYY
1000000000

90