Novi projekt Nove TV, Ljepotice i genijalci, sociološki je eksperiment pred TV kamerama koji spaja naizgled nespojive karaktere u parove koji zajedničkim radom i zalaganjem trebaju savladati različite zabavne zadatke. Novi projekt autora ovog teksta, Ljepotica, sociološki je eksperiment koji spaja naizgled nespojive stvari — reality televiziju i Hrvatsku informatičku olimpijadu — s ciljem stvaranja zabavnog zadatka.

Junakinja ovog zadatka je ljepotica Ena koja je zarobljena u potpunom binarnom stablu dubine N. Svakom čvoru stabla pridružena je vrijednost pa tako korijen stabla ima vrijednost 1. Vrijednost lijevog djeteta čvora vrijednosti x jednaka je 2x, a vrijednost desnog djeteta čvora vrijednosti x jednaka je 2x + 1. Izlaz iz stabla nalazi se u jednom od njegovih listova (čvorova dubine N, koji nemaju djece), a Ena se iz nekog čvora može pomaknuti u neko od njegove djece.

Točan put od korijena do izlaznog lista Ena je morala zapamtiti prije ulaska u korijen stabla. Budući da Ena ima fotografsko pamćenje, bez problema je zapamtila ispravan put, odnosno, poznat joj je ispravan niz od N – 1 koraka “lijevo” ili “desno” koji čini put od korijena do izlaznog lista u stablu. Nažalost, Ena nikako ne može zapamtiti koja je lijeva, a koja desna strana te je za vrijeme svog putovanja točno K puta promijenila svoj stav o tome što znači “lijevo”, a što znači “desno”. Kada Ena promijeni stav, ponaša se u skladu s njim sve do kraja puta ili do idućeg mijenjanja stava. Mijenjanje stava može se dogoditi samo jednom prije svakog koraka u stablu (uključujući prvi). Također, nitko ne zna je li prilikom samog ulaska u korijen stabla Ena imala ispravan stav.

Čelnici Nove TV spasit će izgubljenu Enu ako njen partner genijalac, a to ste Vi, ponudi točan odgovor na sljedeće pitanje: Koliki je zbroj vrijednosti listova u kojima se Ena mogla naći na kraju putovanja ako u obzir uzimamo samo one listove čija je vrijednost veća ili jednaka A i manja ili jednaka B?

Ulazni podaci

U prvom su retku prirodni brojevi N i K iz teksta zadatka (2 ≤ N ≤ 1000, 0 ≤ K ≤ N – 1).

U drugom je retku riječ koja se sastoji od N – 1 znakova ‘L’ i ‘R’ koji redom predstavljaju ispravan put od korijena stabla do izlaznog lista, pri čemu znak ‘L’ označava pomak prema lijevom, a znak ‘R’ pomak prema desnom djetetu.

U trećem je retku broj A iz teksta zadatka u binarnom zapisu bez vodećih nula.

U četvrtom je retku broj B iz teksta zadatka u binarnom zapisu bez vodećih nula.

Ena će sigurno moći završiti putovanje u listu vrijednosti A i listu vrijednosti B.

Izlazni podaci

U jedini redak ispišite traženi zbroj u dekadskom zapisu modulo 1 000 000 007.

Primjeri test podataka

Ulaz

3 0
LR
101
110

Izlaz

11

Ulaz

4 2
LRR
1010
1110

Izlaz

37

Ulaz

5 2
RLLR
10010
10111

Izlaz

82