Long là một cậu bé thích ăn bún bò, vì vậy mà nhà Long có nuôi một con mèo. Kì lạ thay, con mèo này lại rất thích chơi oản tù tì với Long.

Luật của trò chơi oẳn tù tì rất đơn giản:

• Kéo (\('K'\)) thắng Lá (\('L'\))
• Lá (\('L'\)) thắng Búa (\('B'\))
• Búa (\('B'\)) thắng Kéo (\('K'\))

Hôm hay Long mới ăn được bát bún bò hơi nhiều ớt, vì vậy rất hăng máu, muốn oản tù tì với con mèo nhà mình tận \(N\) \((N \leq 10^6)\) cho đỡ cay. Mèo ta rất khôn, không chỉ biết rằng Long đang cay mà còn có thể nhìn trước tương lai xem ở bước thứ \(i\) \((1 \leq i \leq N)\) Long sẽ ra \('K'\), \('B'\) hay \('L'\).

Vì đang rất cay nên một số \(K\) \((1 \leq K \leq N)\) xuất hiện lù lù trên mặt Long. Nếu số ván mèo ta oẳn tù tì thắng Long nhiều hơn \(K\) ván thì kiểu gì hôm sau sẽ phải chuyển nhà vào nồi lẩu.

Mặc dù rất sợ nước (đặc biệt là nước sôi) tuy nhiên mèo ta lại rất hiếu thắng, vì vậy mà phải thắng đúng \(K\) ván mới hả hê. Long muốn chơi rất nhiều ván oẳn tù tì, nhiều đến mức nếu đếm bằng cơm thì mèo ta sẽ lên bàn thờ trước khi lên bàn ăn. Vì vậy nó nhờ các bạn, tính số cách mà mèo có thể thắng đúng \(K\) ván khi chơi oẳn tù tì với Long.

Note: vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho \(10^9 + 7\)

Dữ liệu:

• Dòng đầu tiên gồm \(2\) số nguyên dương \(N\), \(K\)
• Dòng tiếp theo gồm xâu \(S\) \((|S| = N)\), kí tự \(S[i]\) sẽ có giá trị là \(1\) trong \(3\) ký tự \('K'\), \('B'\) hoặc \('L'\)

Kết quả:

• Một dòng duy nhất chứa kết quả bài toán, chia lấy dư cho \(10^9 + 7\)

3 1
KBL

12