B"You are given a binary string s (each character of this string is either 0 or 1). Let's denote the cost of string t as the number of occurences of s in t. For example, if s is 11 and t is 111011, then the cost of t is 3. Let's also denote the Fibonacci strings sequence as follows: Your task is to calculate the sum of costs of all subsequences of the string F(x). Since answer may be large, calculate it modulo 109 xe2 x80 x89+ xe2 x80 x897. The first line contains two integers n and x (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89100, 0 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89x xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89100) -- the length of s and the index of a Fibonacci string you are interested in, respectively. The second line contains s -- a string consisting of n characters. Each of these characters is either 0 or 1. Print the only integer -- the sum of costs of all subsequences of the string F(x), taken modulo 109 xe2 x80 x89+ xe2 x80 x897. "...