시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 512 MB 3 3 3 100.000%

문제

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?

입력

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.

출력

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

서브태스크 1 (8점)

  • K = 0

서브태스크 2 (14점)

  • N ≤ 25

서브태스크 3 (17점)

  • A is the smallest, and B is the greatest value where Ena can finish

서브태스크 4 (61점)

  • no additional constraints

예제 입력 1

3 0
LR
101
110

예제 출력 1

11

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.

예제 입력 2

4 2
LRR
1010
1110

예제 출력 2

37

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

예제 입력 3

5 2
RLLR
10010
10111

예제 출력 3

82

채점

  • 예제는 채점하지 않는다.