Blue and Green is a fictitious sandbox game where you have a line of blue and green marbles. There exists a currency in this game, which you can use to change the assortment of marbles. Each move has its own cost. The following moves are:

• set the colour of a single marble at a cost of ~S~
• rotate all the marbles to the left by 1 (the left-most marble moves to the right end, and everything else moves one place to the left) at a cost of ~L~
• rotate all the marbles to the right by 1 (the right-most marble moves to the left end, and everything else moves one place to the right) at a cost of ~R~
• invert the colour of all the marbles at a cost of ~I~

Find the number of different arrangements of blue and green marbles that can be achieved by using ~M~ or less currency units. All blue marbles are not distinguishable from each other and the same goes for green marbles. This means that if you have the arrangement GBGBGB and you rotate it twice to get GBGBGB, the original and final arrangements are indistinguishable (equivalent).

Hint: try the steps in the listed order for efficiency.

Input Specification

The first line contains two space separated integers ~N~ ~(1 \le N \le 20)~, the number of marbles and ~M~, the amount of currency.

The second line contains four space separated integers ~S~, ~L~, ~R~ and ~I~.

The third line contains a string with ~N~ characters, B for a blue marble or G for a green marble.

~1 \le S, L, R, I, M \le 100~

Note: Test cases are reasonable.

Subtask 1 [5%]

~N \le 5~

Subtask 2 [5%]

~N \le 10~

Subtask 3 [90%]

~N \le 20~

Output Specification

A single integer - the number unique marble arrangements achievable with the amount of currency.

Sample Input 1

2 1
1 2 2 2
BB

Sample Output 1

3

Explanation for Sample Output 1

You can only afford to set the colour of one marble. Thus, you can change the colour of the first or second marble to get the possible arrangements: BB, GB and BG.

Sample Input 2

4 1
1 1 1 1
BGGG

Sample Output 2

8

Explanation for Sample Output 2

You can afford one of the moves. Thus, we get the following unique arrangements:

• BGGG original
• GGGG setting the first marble to green
• BBGG setting the second marble to blue
• BGBG setting the third marble to blue
• BGGB setting the fourth marble to blue
• GBGG rotating the marbles right once
• GGGB rotating the marbles left once
• GBBB inverting all the colours

Sample Input 3

5 5
3 4 4 2
BGGBB

Sample Output 3

14