Ljepotica

Το Beauty and the Geek είναι μια τηλεοπτική σειρά ριάλιτι που διαφημίζεται ότι συνδέει γυναίκες καλλονές και άνδρες geeks με στόχο τη δημιουργία του "The Ultimate Social Experiment". Αυτό το πρόβλημα διαφημίζεται ότι συνδέει την τηλεόραση ριάλιτι και τον ανταγωνιστικό προγραμματισμό με στόχο τη δημιουργία ενός διασκεδαστικού προβλήματος.
Ο ήρωάς μας είναι μια καλλονή η Ena, παγιδευμένη σε ένα πλήρες δυαδικό δέντρο βάθους ~N~. Κάθε κόμβος του δέντρου έχει μια τιμή: η ρίζα του δέντρου έχει τιμή ~1~ και για κάθε κόμβο με τιμή ~x~, το αριστερό του παιδί έχει τιμή ~2x~ και το δεξί του παιδί έχει τιμή ~2x + 1~. H Ena μπορεί να μετακινηθεί από έναν κόμβο σε ένα από τα δύο παιδιά του,με κατεύθυνση προς την έξοδο που βρίσκεται σε ένα από τα φύλλα (κόμβοι βάθους ~N~, χωρίς παιδιά).
H Ena γνωρίζει μια ακριβή διαδρομή από τη ρίζα μέχρι το φύλλο εξόδου. Πιο συγκεκριμένα, ξέρει τη σωστή σειρά των ~N - 1~ κινήσεων, καθεμία από αυτές "αριστερά" ή "δεξιά", που θα την καθοδηγούσαν από τη ρίζα στην έξοδο φύλλο. Δυστυχώς, η Ena δεν είναι σίγουρη ποια πλευρά είναι αριστερή και ποια δεξιά. Ως εκ τούτου, κατά τη διάρκεια του ταξιδιού της, άλλαξε γνώμη ακριβώς ~K~ φορές για την έννοια του "αριστερά" και "δεξιά". Όταν αλλάζει γνώμη, κινείται ανάλογα μέχρι το τέλος του ταξιδιού (ένας κόμβος φύλλου) ή μέχρι την επόμενη αλλαγή γνώμης. Η αλλαγή γνώμης της Ena μπορεί να συμβεί μόνο μία φορά πριν από κάθε κίνηση στο δέντρο (συμπεριλαμβανομένης της πρώτης). Επίσης, κανείς δεν ξέρει αν η Ena είχε κατά νου τις σωστές πλευρές όταν έμπαινε στη ρίζα του δέντρου.
Οι παραγωγοί της τηλεοπτικής εκπομπής θα σώσουν τη χαμένη Ena αν εσύ, ο geek σύντροφός της, απαντήσεις σωστά στην ακόλουθη ερώτηση: Ποιο είναι το άθροισμα των τιμών των φύλλων όπου η Ena μπορεί να ολοκληρώσει το ταξίδι της, λαμβάνοντας υπόψη μόνο τα φύλλα με τιμές τουλάχιστον ~A~ και το πολύ ~B~;

Είσοδος

Η πρώτη γραμμή περιέχει ακέραιους ~N~ και ~K~ από την περιγραφή της εργασίας ~(2 \le N \le 1\,000,\,0 \le K \le N - 1)~.
Στη δεύτερη γραμμή υπάρχει μια λέξη που περιέχει ~N - 1~ χαρακτήρες «~L~» (αριστερά) και «~R~» (δεξιά) που αντιπροσωπεύουν τη σωστή διαδρομή από τη ρίζα προς το φύλλο εξόδου.
Η τρίτη γραμμή περιέχει τον αριθμό ~A~ από την περιγραφή της εργασίας, σε δυαδική μορφή χωρίς να αρχίζει με μηδέν.
Η τέταρτη γραμμή περιέχει τον αριθμό ~B~ από την περιγραφή της εργασίας, σε δυαδική μορφή χωρίς να αρχίζει με μηδέν.
Η Ena θα μπορέσει να τερματίσει στα φύλλα ~A~ και ~B~.

Έξοδος

Εκτυπώστε το απαιτούμενο άθροισμα ως δεκαδικό ακέραιο modulo ~1\,000\,000\,007~.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	8	~K = 0~
2	14	~N \le 25~
3	17	~A~ είναι η μικρότερη, και ~B~ είναι η μεγαλύτερη τιμή στην οποία μπορεί να τερματίσει η Ena.
4	61	Κανένας περαιτέρω περιορισμός.

Παραδείγματα

input

3 0
LR
101
110

output

11

Επεξήγηση του 1ου παραδείγματος:

Η Ena δεν θα αλλάξει ποτέ γνώμη, αλλά δεν ξέρουμε αν είχε το σωστό αριστερά/δεξιά στο μυαλό από την αρχή. Άρα, μπορεί να ακολούθησε σωστά τις οδηγίες και πάει προς το αριστερό και μετά προς το δεξί παιδί. Ή, μπορεί να ακολούθησε τις αντίστροφες οδηγίες, πηγαίνοντας πρώτα στο δεξί παιδί και μετά στο αριστερό παιδί. Τα φύλλα που φτάνει έχουν τιμές ~5~ και ~6~ που αντιστοιχούν στα ~A~ και ~B~, άρα η απάντηση είναι ~5 + 6~.

input

4 2
LRR
1010
1110

output

37

Επεξήγηση του 2ου παραδείγματος:

Πιθανές διαδρομές της Ena: (αριστερά, αριστερά, αριστερά), (αριστερά, αριστερά, δεξιά), (αριστερά, δεξιά, αριστερά), (δεξιά, αριστερά, δεξιά), (δεξιά, δεξιά, αριστερά) ή (δεξιά, δεξιά, δεξιά).

input

5 2
RLLR
10010
10111

output

82