CF946F Fibonacci String Subsequences

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

Print the only integer — the sum of costs of all subsequences of the string $ F(x) $ , taken modulo $ 10^{9}+7 $ .