The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

Codeforces Round 129 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dp

*2400

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Little Elephant and Retro Strings

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe Little Elephant has found a ragged old black-and-white string *s* on the attic.

The characters of string *s* are numbered from the left to the right from 1 to |*s*|, where |*s*| is the length of the string. Let's denote the *i*-th character of string *s* as *s*_{i}. As the string is black-and-white, each character of the string is either letter "B", or letter "W". Unfortunately, the string is very old and some characters are damaged. The damaged positions are denoted as "X".

The Little Elephant in determined to restore the string and hang it on the wall. For that he needs to replace each character "X" by a "B" or a "W". The string must look good on the wall, so it must be beautiful. The Little Elephant considers a string beautiful if it has two non-intersecting substrings of a given length *k*, such that the left one fully consists of characters "B", and the right one fully consists of characters "W". More formally, there are four integers *a*, *b*, *c*, *d* (1 ≤ *a* ≤ *b* < *c* ≤ *d* ≤ |*s*|; *b* - *a* + 1 = *d* - *c* + 1 = *k*) such that *s*_{i} = "B" (*a* ≤ *i* ≤ *b*) and *s*_{j} = "W" (*c* ≤ *j* ≤ *d*).

Help the Little Elephant find the number of different beautiful strings he can obtain from string *s*. Two strings are considered different if there is such position, where the character in the first string differs from the corresponding character in the second string. If this string doesn't contain characters «X» and it is already beautiful — the answer is 1.

As the answer can be rather large, print it modulo 1000000007 (10^{9} + 7).

Input

The first line contains two space-separated integers *n* and *k* (1 ≤ *k* ≤ *n* ≤ 10^{6}). The second line contains string *s*. String *s* has length *n* and only consists of characters "W", "B" and "X".

Output

On a single line print an integer — the answer to the problem modulo 1000000007 (10^{9} + 7).

Examples

Input

3 2

XXX

Output

0

Input

4 2

XXXX

Output

1

Input

10 2

XXBXXWXXXX

Output

166

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/26/2024 01:54:17 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|