E - Swap Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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

出力

答えを出力せよ。

入力例 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

Score : 500 points

Problem Statement

Given is a string S consisting of K, E, Y.

How many strings are there that can be obtained with at most K swaps of two adjacent characters in S?

Constraints

  • 2 \leq |S| \leq 30
  • 0 \leq K \leq 10^9
  • S consists of K, E, Y.

Input

Input is given from Standard Input in the following format:

S
K

Output

Print the answer.

Sample Input 1

KEY
1

Sample Output 1

3

With at most one swap, there are three strings that can be obtained: KEY, EKY, KYE.

Sample Input 2

KKEE
2

Sample Output 2

4

With at most two swaps, there are four strings that can be obtained: KKEE, KEKE, EKKE, KEEK.

Sample Input 3

KKEEYY
1000000000

Sample Output 3

90