CF204D Little Elephant and Retro Strings

The 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

The first line contains two space-separated integers $ n $ and $ k $ $ (1

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