문제
미녀와 야수는 요즘 유행하는 인기 TV 쇼의 제목이다.
이 TV 쇼에서 게스트로 초대된 미녀 영화배우는, 깊이가 N인 이진 트리 미로에 갇힌다.
게스트는 이진 트리의 루트 노드(정점)에서 시작하여, 출구가 있는 리프(자식이 없는 노드)까지 걸어가며,이 모습이 생중계되는 방식이다.
각 리프 노드에는 출구가 있으며, 출구 밖에는 야수가 있을 수도 있고, 동현, 딧불, 건우 등의 유명 남배우들이 대기하고 있을 수도 있다.
이진 트리의 각 노드는 고유한 번호가 있으며, 루트 노드가 1번이고, 각 노드 X의 왼쪽 자식은 2X, 오른쪽 자식은 2X + 1의 번호를 가지고 있다.
사실 우리의 미녀 게스트는, 방송 특성상 몇 번째 방에서 어느 방향으로 가야 하는지를 이미 지령 받은 상태로 시작한다.
첫 번째 방에서는 왼쪽, 두 번째 방에서는 오른쪽… 이런 식으로 말이다.
문제는 불쌍한 게스트가 “왼쪽”이 어느 방향이고 “오른쪽”이 어느 방향인지 헷갈려 한다는 것이다.
여러분이 게스트라고 상상해 보자.
트리 구조대로라면 트리의 왼쪽 자식이 왼쪽 방향이겠지만, (그림1)
게스트가 노드 위에 서서 자식 노드 방향으로 앞을 바라보면, 오른쪽 자식이 왼쪽으로 보일 것이다. (그림 2)
그림1
그림 2
그래서 게스트는 진행 도중에 K번, 그림 1처럼 트리 구조대로 좌우를 판단할지, 아니면 그림 2처럼 자기 시선에서 좌우를 판단할지에 관하여 마음을 바꾼다.
마음의 변화는 각 노드에서 최대 한 번씩만 일어난다.
시작하자마자 루트 노드에서 마음을 바꿀 수도 있다.
TV쇼 시작 전에는, 게스트의 마음(방향감각)이 그림 1과 같은 트리 구조 기준일 수도 있고, 그림 2와 같은 자기 시선 기준일수도 있다.
미남 배우들은 리프 노드 중, 그 번호가 A이상 B이하인 노드에 있다.
미녀 게스트가 정확히 K번 마음을 바꿔서 갈 수 있는 리프 노드 중, A이상 B이하인 노드의 번호의 합을 출력하는 프로그램을 작성하라.
답이 클 수 있으므로, 10억 7로 나눈 나머지를 출력한다.
입력
첫 줄에 N과 K가 공백을 사이에 두고 주어진다. N은 트리의 깊이(루트에서 리프까지의 노드 개수)이고, K는 게스트가 마음을 바꾸는 횟수이다.(2≤N≤1,000 , 0≤K≤N-1)
둘째 줄에 N-1개의 문자로 이루어진 문자열이 들어온다. 문자는 ‘L’ 또는 ‘R’이며, 앞에서부터 각 갈림길에서 미녀가 지령 받은 방향을 나타낸다. L은 왼쪽, R은 오른쪽을 나타낸다.
셋째 줄에 A가 2진수로 주어지며, 맨 앞자리는 1이다.
넷째 줄에 B가 2진수로 주어지며, 맨 앞자리는 1이다.
부분문제의 제약 형식
부분문제 1: 전체 100점 중 8점에 해당하며 K=0이다.
부분문제 2: 전체 100점 중 14점에 해당하며 N≤25이다.
부분문제 3: 전체 100점 중 17점에 해당하며, A는 가장 왼쪽에 있는 리프 노드, B는 가장 오른쪽에 있는 리프 노드이다.
부분문제 4: 전체 100점 중 61점에 해당하며, 주어진 제약 외 아무 제약 조건이 없다.
출력
예제1
30
LR
101
110
11
예제2
42
LRR
1010
1110
37
예제3
52
RLLR
10010
10111
82