Beauty and the Geek is a reality television series advertised as connecting female beauties and male geeks with the goal of creating "The Ultimate Social Experiment". This task is advertised as connecting reality TV and competitive programming with the goal of creating a fun task.

Our hero is a beauty Ena, trapped in a complete binary tree of depth $N$. Each node of the tree has a value: root of the tree has a value of $1$, and for each node with a value of $x$, its left child has a value of $2x$, and its right child has a value of $2x+1$. Ena can move from a node to one of its two children, heading for the exit which is located in one of the leaves (nodes of depth $N$, with no children).

Ena knows an exact path from the root to the exit leaf. More precisely, she knows the correct sequence of $N-1$ moves, each of them being "left" or "right", which would guide her from the root to the exit leaf. Unfortunately, Ena is not sure which side is left and which side is right. Therefore, during her trip, she changed her mind exactly $K$ times about the meaning of "left" and "right". When she changes her mind, she moves accordingly until the end of the trip (a leaf node) or until the next change of mind. Ena's change of mind can happen only once before each move in the tree (including the first one). Also, nobody knows whether Ena had correct sides in mind while entering the root of the tree.

The producers of the TV show will save the lost Ena if you, her geek partner, answer correctly to the following question: What is the sum of leaf values where Ena can finish her trip, considering only leaves with values of at least $A$ and at most $B$?

Input Specification

The first line contains integers $N$ and $K$ from the task description $(2\le N\le 1000,0\le K\le N-1)$.

In the second line there is a word containing $N-1$ characters L (left) and R (right) representing the correct path from the root to the exit leaf.

The third line contains the number $A$ from the task description, in binary form without leading zeros.

The fourth line contains the number $B$ from the task description, in binary form without leading zeros.

Ena will be able to finish in leaves $A$ and $B$.

Output Specification

Output the required sum as a decimal integer modulo $1000000007$.

Constraints

Subtask	Points	Constraints
1	8	$K=0$
2	14	$N\le 25$
3	17	$A$ is the smallest, and $B$ is the greatest value where Ena can finish.
4	61	No additional constraints.

Sample Input 1

3 0
LR
101
110

Sample Output 1

11

Explanation of Sample Output 1

Ena will never change her mind, but we don't know if she had the correct left/right sides in mind from the beginning. So, she might have followed the instructions correctly and go to the left, and then the right child. Or, she might have followed the inverse instructions, going first to the right child and then to the left child. The arriving leaves have values $5$ and $6$ which correspond to $A$ and $B$, so the answer is $5+6$.

Sample Input 2

4 2
LRR
1010
1110

Sample Output 2

37

Explanation of Sample Output 2

Possible Ena's paths: $(\text{left},\text{left},\text{left})$, $(\text{left},\text{left},\text{right})$,$(\text{left},\text{right},\text{left})$, $(\text{right},\text{left},\text{right})$, $(\text{right},\text{right},\text{left})$, or $(\text{right},\text{right},\text{right})$.

Sample Input 3

5 2
RLLR
10010
10111

Sample Output 3

82