← 返回题目列表

Codeforces · 946/F

F. 斐波那契字符串子序列

中文机器翻译题面 查看原题

给定一个二进制字符串 s(该字符串的每个字符不是 0 就是 1)。

让我们将字符串 t 的成本表示为 s 在 t 中出现的次数。例如,如果 s 为 11,t 为 111011,则 t 的成本为 3。

我们还将斐波那契字符串序列表示如下:

- F(0) 为 0;
- F(1) 为 1;
- F(i) = F(i - 1) + F(i - 2) 如果 i > 1,其中  +  表示两个字符串的串联。

你的任务是计算字符串 F(x) 的所有子序列的成本总和。由于答案可能很大,请以 109 + 7 为模进行计算。

输入

第一行包含两个整数 n 和 x (1 ≤ n ≤ 100, 0 ≤ x ≤ 100) — 分别是 s 的长度和您感兴趣的斐波那契字符串的索引。

第二行包含 s — 由 n 个字符组成的字符串。这些字符中的每一个都是 0 或 1。

输出

打印唯一的整数 — 字符串 F(x) 的所有子序列的成本总和,以 109 + 7 为模。

示例

输入 #1

2 4
11

输出 #1

14

输入 #2

10 100
1010101010

输出 #2

553403224