Beauty and the Geek là một chương trình truyền hình thực tế được quảng cáo là kết nối những người đẹp nữ và những người đam mê khoa học nam với mục tiêu tạo ra "Thí nghiệm xã hội tối thượng". Nhiệm vụ này được quảng cáo là kết nối truyền hình thực tế và lập trình cạnh tranh với mục tiêu tạo ra một nhiệm vụ thú vị.

Nhân vật chính của chúng ta là một người đẹp tên Ena, bị mắc kẹt trong một cây nhị phân hoàn chỉnh có độ sâu ~N~. Mỗi nút trong cây có một giá trị: gốc của cây có giá trị là ~1~, và với mỗi nút có giá trị ~x~, con trái của nó có giá trị là ~2x~, và con phải của nó có giá trị là ~2x + 1~. Ena có thể di chuyển từ một nút đến một trong hai con của nó, hướng tới lối ra nằm ở một trong các lá (các nút ở độ sâu ~N~, không có con).

Ena biết một đường dẫn chính xác từ gốc đến lá thoát. Cụ thể, cô ấy biết chuỗi chính xác của ~N-1~ bước, mỗi bước là “trái” hoặc “phải”, dẫn cô ấy từ gốc đến lá thoát. Tuy nhiên, Ena không chắc chắn bên nào là trái và bên nào là phải. Do đó, trong chuyến đi của mình, cô đã thay đổi ý kiến chính xác ~K~ lần về ý nghĩa của “trái” và “phải”. Khi cô thay đổi ý kiến, cô di chuyển theo hướng mới cho đến khi kết thúc chuyến đi (một nút lá) hoặc cho đến lần thay đổi ý kiến tiếp theo. Ena có thể thay đổi ý kiến chỉ một lần trước mỗi bước trong cây (bao gồm cả bước đầu tiên). Ngoài ra, không ai biết liệu Ena có đúng bên trái và phải khi vào gốc của cây hay không.

Nhà sản xuất chương trình truyền hình sẽ cứu Ena bị lạc nếu bạn, đối tác thông minh của cô ấy, trả lời đúng câu hỏi sau: Tổng giá trị của các lá mà Ena có thể kết thúc chuyến đi là bao nhiêu, chỉ xét các lá có giá trị từ ~A~ đến ~B~ (bao gồm ~A~ và ~B~)?

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~K~ từ mô tả nhiệm vụ ~(2 \leq N \leq 1000, 0 \leq K \leq N – 1)~.
• Dòng thứ hai chứa một chuỗi ~N – 1~ ký tự ~L~ (trái) và ~R~ (phải) đại diện cho đường dẫn chính xác từ gốc đến lá thoát.
• Dòng thứ ba chứa số ~A~ từ mô tả nhiệm vụ, ở dạng nhị phân không có số ~0~ đứng đầu.
• Dòng thứ tư chứa số ~B~ từ mô tả nhiệm vụ, ở dạng nhị phân không có số ~0~ đứng đầu.

Output

In ra tổng giá trị yêu cầu dưới dạng số nguyên thập phân modulo ~10^9 + 7~.

Chú thích

• ~8 \%~ số điểm thỏa mãn ~K = 0~.
• ~14 \%~ số điểm thỏa mãn ~K = 25~.
• ~17 \%~ số điểm thỏa mãn ~A~ là số nhỏ nhất, ~B~ là số lớn nhất.

Sample Input 1

3 0
LR
101
110

Sample Ouput 1

11

Sample Input 2

4 2
LRR
1010
1110

Sample Ouput 2

37

Sample Input 3

5 2
RLLR
10010
10111

Sample Ouput 3

82

Giải thích

Mô tả mẫu đầu tiên: Ena sẽ không bao giờ thay đổi suy nghĩ của mình, nhưng chúng ta không biết liệu cô ấy đã có ý tưởng đúng về phía trái/phải ngay từ đầu hay không. Vì vậy, cô ấy có thể đã làm theo hướng dẫn một cách chính xác và đi sang trái, rồi đến con bên phải. Hoặc, cô ấy có thể đã làm theo hướng dẫn đảo ngược, đi trước đến con bên phải rồi sau đó là con bên trái. Các lá đến có giá trị ~5~ và ~6~ tương ứng với ~A~ và ~B~, vì vậy câu trả lời là ~5 + 6~.

Mô tả mẫu thứ hai: Các con đường có thể của Ena: (trái, trái, trái), (trái, trái, phải), (trái, phải, trái), (phải, trái, phải), (phải, phải, trái), hoặc (phải, phải, phải).