Go back to Challenges list

## Squad Formation Curse

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.

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`