CF946F Fibonacci String Subsequences

给定一个二进制字符串 $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$ 取模后的结果。

第一行包含两个整数 $n$ 和 $x$（$1 \leq n \leq 100$，$0 \leq x \leq 100$），分别表示 $s$ 的长度和你关心的斐波那契字符串的下标。 第二行包含字符串 $s$，由 $n$ 个字符组成，每个字符都是 $0$ 或 $1$。

输出一个整数，表示 $F(x)$ 的所有子序列的代价之和，对 $10^9+7$ 取模。

由 ChatGPT 4.1 翻译