Welcome!

×

...or use your e-mail

Go back to Challenges list

Challenge

Squad Formation Curse

Created by
There was a curse in squad formation!
To begin with, a squad is a line, of size N, with people. The people will be distinguished in two types: Lieutenant (L)
and Rectruit (R).
There are some places which are already assigned. And now you want to determine in how many ways you can complete the squad formation, but DON'T forget the curse! You should be asking, what curse?
The curse says that if there are any K recruits together, all people are gone die and you don't want that.
Your answer should be modulo 1000000007.

Input Format
The input will have three parameters separated by spaces. The first two are integers, N and K (2 <= K <= N <= 1.000.000). The third one is a string constituted by ’L’ (meaning that there is a lieutenant in that position), ’R’ (meaning that there is a recruit in that position) or ’ ?’ (meaning that in that place could be either a lieutenant or a recruit).

Output Format
Your answer should be a single line with a integer that represent the number of ways of completing the line without everyone die.

Sample Input
4 3
R??R


Sample Output
3

Memory Limit
512M


Sign Up or Login to solve this Code Challenge