题目描述

译自 COI 2019 T2「LJEPOTICA」

Beauty and the Geek 是一档电视真人秀节目。这档节目旨在将美女和男性极客联系起来，达到「终极社会实验」的目的。这道题旨在将电视节目和编程竞赛联系起来，达到出一道有趣的题的目的。

我们的主人公是小姐姐 Ena，她现在被困在一棵深度为 $N$ 的完全二叉树中。树上每一个节点都有一个值：根节点的值为 $1$，对于每个值为 $x$ 的节点，其左儿子的值为 $2x$，右儿子的值为 $2x+1$。Ena 可以从一个节点出发到它的某个儿子去，她要前往位于某一个叶子节点的出口（叶子节点指深度为 $N$ 且没有儿子的节点）。

Ena 确切地知道一条从根节点到出口叶子节点的路径，更确切地说，她知道一个正确的长为 $N-1$ 的移动序列，每一项为「左」或「右」，它可以引导 Ena 从根节点走到出口处。遗憾的是，Ena 分不清左右。因此，在她前往出口的途中，她恰好改变了 $K$ 次「左」和「右」表示的方向。在她改变主意后，她会保持她认为的左右方向一直走到一个叶子节点或下一次改变主意。Ena 只能在移动之前改变主意（包括第一个节点）一次。并且，没人知道 Ena 在进入根节点的时候她认为的左右是否是正确的方向。

节目制作人将拯救迷路的 Ena。但是需要你，Ena 的极客同伴，正确回答如下问题：只考虑值在 $A$ 到 $B$（包括两端）中的叶子节点，Ena 结束移动的叶子节点值的和是多少。

输入格式

第一行两个整数 $N,K$，意义如题目描述；

接下来一行包含一个长为 $N-1$ 的字符串，只包含字母 L 和 R，表示从根到有出口的叶子节点的一条路径；

第三行一个 $01$ 串，为 $A$ 的二进制表示，无前导 $0$，意义如题目描述；

第四行一个 $01$ 串，为 $B$ 的二进制表示，无前导 $0$，意义如题目描述。

输出格式

输出所求的和对 $10^9+7$ 取模后的值。

3 0
LR
101
110

11

4 2
LRR
1010
1110

37

5 2
RLLR
10010
10111

82

提示

样例 1 解释

Ena 不会改变她对左右方向的认识，但是我们不知道她在进入根节点之前认识到的左右方向是否正确。因此她可能按照正确的左右方向先左后右走到节点 $5$，也可能先右后左走到节点 $6$，两个叶子节点分别为 $A$ 和 $B$，因此答案为 $5+6=11$。

样例 2 解释

Ena 经过路径的可能（按正确的左右方向）：

• $\{\texttt{L, L, L}\}$；
• $\{\texttt{L, L, R}\}$；
• $\{\texttt{L, R, L}\}$；
• $\{\texttt{R, L, R}\}$；
• $\{\texttt{R, R, L}\}$；
• $\{\texttt{R, R, R}\}$。

数据范围

对于全部数据，$2\le N\le 10^3,0\le K\le N-1$。保证 Ena 可以到达值为 $A$ 和 $B$ 的两个叶子节点。

详细子任务附加限制及分值如下表：