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: F (0) is 0 ; F (1) is 1 ; F ( i ) = F ( i - 1) + F ( i - 2) if i > 1 , where + means the concatenation of two strings. 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 10 9 + 7 . The first line contains two integers n and x ( 1 ≤ n ≤ 100 , 0 ≤ x ≤ 100 ) — 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 10 9 + 7 .