미녀와 괴짜
시간 제한0.5초메모리 제한512 MB
완전 이진 트리에서 좌우 경로와 좌우 의미를 정확히 K번 바꾸는 상황이 주어질 때, [A,B] 구간에 들어오는 도달 가능한 리프 값의 합을 1e9+7로 나눈 나머지를 구한다.
문제
Beauty and the Geek는 여성 미녀와 남성 괴짜를 이어 주는 리얼리티 TV 프로그램으로, "궁극의 사회적 실험"을 만드는 것을 목표로 내세운다. 이 문제는 리얼리티 TV와 경쟁 프로그래밍을 이어 재미있는 문제를 만드는 것을 목표로 한다.
주인공은 깊이 N인 완전 이진 트리에 갇힌 미녀 Ena이다. 트리의 각 노드에는 값이 있다. 뿌리의 값은 1이고, 값이 x인 노드의 왼쪽 자식은 2x, 오른쪽 자식은 2x + 1이다. Ena는 한 노드에서 두 자식 중 하나로 이동할 수 있으며, 출구는 깊이 N인 잎(자식이 없는 노드) 중 한 곳에 있다.
Ena는 뿌리에서 출구 잎까지의 정확한 경로를 알고 있다. 즉, 뿌리에서 출구 잎까지 안내하는 N - 1개의 이동 순서, 각각 "왼쪽" 또는 "오른쪽"을 알고 있다. 안타깝게도 Ena는 어느 쪽이 왼쪽이고 어느 쪽이 오른쪽인지 확신하지 못한다. 그래서 여행 중에 "왼쪽"과 "오른쪽"의 의미에 대해 정확히 K번 마음을 바꾼다. 마음을 바꾸면 여행이 끝나거나(잎 노드에 도착하거나) 다음 번 마음을 바꿀 때까지 그에 따라 이동한다. Ena가 마음을 바꾸는 것은 트리에서 각 이동 직전에 한 번씩만 일어날 수 있다(첫 번째 이동도 포함). 또한 Ena가 트리의 뿌리에 들어올 때 올바른 방향을 염두에 두고 있었는지는 아무도 모른다.
TV 쇼의 제작진은 괴짜 파트너인 당신이 다음 질문에 정확히 답하면 길을 잃은 Ena를 구해 줄 것이다. Ena가 여행을 마칠 수 있는 잎 값 중에서, 값이 A 이상 B 이하인 잎만 고려했을 때 그 합은 얼마인가?
입력
첫째 줄에는 문제 설명의 정수 N과 K가 주어진다(2 ≤ N ≤ 1000, 0 ≤ K ≤ N – 1).
둘째 줄에는 뿌리에서 출구 잎까지의 올바른 경로를 나타내는 N – 1개의 문자 'L'(왼쪽)과 'R'(오른쪽)로 이루어진 단어가 주어진다.
셋째 줄에는 문제 설명의 수 A가 이진수 형태로, 앞의 0 없이 주어진다.
넷째 줄에는 수 B가 이진수 형태로, 앞의 0 없이 주어진다.
Ena는 잎 A와 B에서 여행을 마칠 수 있다.
출력
필요한 합을 십진 정수로 1 000 000 007로 나눈 나머지를 출력한다.