给定一个二进制字符串 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