题目描述

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?

Beauty and the Geek 是一部真人秀电视连续剧，宣传将女性美女和男性极客联系起来 以创建“终极社会实验”为目标。这项任务被宣传为连接现实 电视和竞争性节目，目的是创造一个有趣的任务。

我们的主人公是美女Ena，被困在一棵深度为N的完全二叉树中。树的每个节点都有一个 value：树的根的值为 1，对于每个值为 x 的节点，其左子节点的值为 2x，其右子节点的值为 2x + 1。 Ena 可以从一个节点移动到它的两个子节点之一， 前往位于其中一片叶子中的出口（深度为 N 的节点，没有子节点）。

Ena 知道从根到出口叶的确切路径。更准确地说，她知道正确的顺序 N – 1 个动作，每个动作都是“左”或“右”，这将引导她从根部到出口 叶子。不幸的是，Ena 不确定哪一边是左边，哪边是右边。因此，在她的旅途中， 她对“左”和“右”的含义改变了 K 次。当她改变她 心，她会相应地移动，直到旅行结束（叶节点）或直到下一次改变主意。 在树中的每一步（包括第一次）之前，Ena 的改变主意只能发生一次。

此外，没有人知道惠那在进入树根时是否有正确的想法。

如果你，她的极客搭档，正确回答 以下问题：仅考虑叶子，Ena 可以完成旅行的叶子值的总和是多少 具有至少 A 和最多 B 的值？

输入格式

The first line contains integers N and K from the task description (2 ≤ N ≤ 1000, 0 ≤ K ≤ 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.

第一行包含来自任务描述的整数 N 和 K (2 ≤ N ≤ 1000, 0 ≤ K ≤ N – 1)。 在第二行有一个包含 N – 1 个字符的单词“L”（左）和“R”（右）代表 从根到出口叶的正确路径。

第三行包含任务描述中的数字 A，以不带前导零的二进制形式。

第四行包含任务描述中的数字 B，以不带前导零的二进制形式。

Ena 将能够在叶子 A 和 B 中完成。

输出格式

Output the required sum as a decimal integer modulo 1 000 000 007.

样例 #1

样例输入 #1

3 0
LR
101
110

样例输出 #1

11

样例 #2

样例输入 #2

4 2
LRR
1010
1110

样例输出 #2

37

样例 #3

样例输入 #3

5 2
RLLR
10010
10111

样例输出 #3

82

提示

First sample description:

Ena will never change her mind, but we don't known 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.

Ena 永远不会改变主意，但我们不知道她是否有正确的想法 从一开始就记住左/右侧。 所以，她可能正确地遵循了指示，并且 去左边，然后是右边的孩子。 或者，她可能按照相反的指示，先走 到右孩子，然后到左孩子。 到达的叶子的值 5 和 6 对应于 A 和 B，所以答案是 5 + 6。

Second sample description:

Possible Ena's paths: (left, left, left), (left, left, right), (left, right, left), (right, left, right), (right, right, left), or (right, right, right).