《美女与极客》（Beauty and the Geek）是一档真人秀电视节目，宣传口号是将美女与极客联系在一起，以创造“终极社会实验”。本题也旨在将真人秀与算法竞赛结合，以创造一道有趣的题目。
我们的主角是一位名叫 Ena 的美女，她被困在一棵深度为 $N$ 的完全二叉树中。树中的每个节点都有一个权值：树根的权值为 $1$；对于权值为 $x$ 的节点，其左子节点的权值为 $2x$，右子节点的权值为 $2x + 1$。Ena 可以从一个节点移动到它的两个子节点之一，向位于叶子节点（深度为 $N$ 且没有子节点的节点）之一的出口前进。
Ena 知道从根节点到出口叶子节点的准确路径。更具体地说，她知道由 $N - 1$ 次移动组成的正确序列，每次移动为“左”（left）或“右”（right），这可以引导她从根节点到达出口叶子节点。不幸的是，Ena 不确定哪边是左，哪边是右。因此，在她的旅途中，她对于“左”和“右”的定义正好改变了 $K$ 次想法。当她改变想法时，她会按照新的定义移动，直到旅途结束（到达叶子节点）或下一次改变想法。Ena 的想法改变只能在每次移动（包括第一次移动）之前发生至多一次。此外，没有人知道 Ena 在进入树根时，脑海中的左右方向是否正确。
如果你——她的极客搭档——能够正确回答以下问题，电视节目的制作人就会营救迷路的 Ena：在所有 Ena 可能结束旅途的叶子节点中，权值至少为 $A$ 且至多为 $B$ 的叶子节点的权值之和是多少？
输入格式
第一行包含两个整数 $N$ 和 $K$，含义如题面所述（$2 \le N \le 1000$，$0 \le K \le N - 1$）。
第二行包含一个长度为 $N - 1$ 的字符串，仅由字符 'L'（左）和 'R'（右）组成，表示从根节点到出口叶子节点的正确路径。
第三行包含一个二进制数 $A$，不含前导零。
第四行包含一个二进制数 $B$，不含前导零。
保证 $A$ 和 $B$ 是 Ena 可以到达的叶子节点。
输出格式
输出所求的和，以十进制整数形式输出，对 $1\,000\,000\,007$ 取模。
子任务
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 8 | $K = 0$ |
| 2 | 14 | $N \le 25$ |
| 3 | 17 | $A$ 是 Ena 可能到达的最小权值，且 $B$ 是 Ena 可能到达的最大权值 |
| 4 | 61 | 无附加限制 |
样例
输入样例 1
3 0 LR 101 110
输出样例 1
11
输入样例 2
4 2 LRR 1010 1110
输出样例 2
37
输入样例 3
5 2 RLLR 10010 10111
输出样例 3
82
说明
样例 1 说明
Ena 永远不会改变她的想法，但我们不知道她一开始脑海中的左右方向是否正确。因此，她可能正确地遵循了指令，先向左走，然后向右走；或者，她可能遵循了相反的指令，先向右走，然后向左走。到达的叶子节点权值分别为 $5$ 和 $6$，对应于 $A$ 和 $B$，因此答案为 $5 + 6 = 11$。
样例 2 说明
Ena 可能的路径有：（左，左，左）、（左，左，右）、（左，右，左）、（右，左，右）、（右，右，左）或（右，右，右）。