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 109 + 7.

给你一个二进制字符串 $ s $（该字符串的每个字符均为 0 或 1）。

我们定义字符串 $ t $ 的代价为 $ s $ 在 $ t $ 中作为子串出现的次数。例如，若 $ s = 11 $，$ t = 111011 $，则 $ t $ 的代价为 3。

我们还定义斐波那契字符串序列如下：

• $ F(0) $ 是字符串 0；
• $ F(1) $ 是字符串 1；
• 当 $ i > 1 $ 时，$ F(i) = F(i-1) + F(i-2) $，其中 $ + $ 表示两个字符串的拼接。

你的任务是计算字符串 $ F(x) $ 的所有子序列的代价之和。由于答案可能很大，请对 $ 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.

第一行包含两个整数 $n$ 和 $x$（$1 \leq n \leq 100$，$0 \leq x \leq 100$），分别表示字符串 $s$ 的长度以及你所关注的斐波那契字符串的索引。

第二行包含字符串 $s$，它由 $n$ 个字符组成，每个字符均为 0 或 1。

Print the only integer — the sum of costs of all subsequences of the string F(x), taken modulo 109 + 7.

输出唯一的整数——字符串 $F(x)$ 的所有子序列的代价之和，对 $10^9 + 7$ 取模。