Beauty and the Geek

Ena, our heroine, is trapped in a complete binary tree of depth N. The tree is numbered as follows: the root is 1, and for any node with value x, its left child is 2x and right child is 2x+1. A leaf is any node at depth N (which has no children).

Before entering the tree, Ena is given a correct moving sequence of length N-1 consisting of the letters L (left) and R (right) that would lead from the root to a designated exit leaf. However, Ena cannot distinguish left from right. On her way, exactly K times she changes her mind about which way to go. More precisely, at any node (including before the very first move) she may decide to flip her interpretation of the instructions. When she does, she continues to follow her (flipped) interpretation until she changes her mind again. Note that nobody knows whether her initial understanding of the directions is correct or if it is inverted.

The effective decision on move i is determined by her current state and the intended move; if her current state is 0 (i.e. her interpretation is correct) then the actual move is the same as the letter in the sequence; if her state is 1 (i.e. her interpretation is flipped) then she takes the opposite move (L becomes R, and R becomes L). That is, if we let r[i] be 0 if the i-th intended move is L and 1 if it is R, then the effective bit d[i] is given by $$d[i] = r[i] \oplus b_i,$$

where b_i is the current state (either 0 or 1) and ( \oplus ) denotes the XOR operator.

Since the tree is complete and the moves determine the path uniquely, one may observe that if we interpret an effective move of L as 0 and R as 1, the final leaf value will be $$ \text{value} = 2^{N-1} + \sum_{i=1}^{N-1} d[i] \cdot 2^{N-1-i}. $$

Your task is: considering only those leaves whose values lie in the interval [A, B] (inclusive), compute the sum of the final leaf values that Ena could possibly end at after exactly K flips. (Note that the two possible initial interpretations, correct or flipped, must both be taken into account and only outcomes reached with exactly K flips are valid.)

## inputFormat

The input consists of three parts:

1. The first line contains two integers N and K (N is the depth of the tree and K is the exact number of times Ena changes her mind).
2. The second line contains a string of length N-1 made up of the characters L and R that represents the intended moving sequence from the root to the exit leaf.
3. The third line contains two integers A and B specifying the range of leaf values to be considered.

## outputFormat

Output a single integer, which is the sum of all possible final leaf node values (each value counted only once) that lie in the interval [A, B].

## sample

3 1
LR
5 6

11

$$