Fibonacci String Subsequences
题意翻译
定义斐波那契字符串:
- $F(0)="0"$
- $F(1)="1"$
- $F(i)=F(i-1)+F(i-2),i>1$
其中,"+"表示将两个字符串首尾相接拼成一个新字符串。
给出一个长度为$n(n\le 100)$的字符串$s$(只包含字符$0,1$)和$x$($x\le 100$),求出$s$在$F(x)$的**所有子序列**中作为子串的出现次数,答案模$10^9 +7$。
题目描述
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<=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.
输出格式
Print the only integer — the sum of costs of all subsequences of the string $ F(x) $ , taken modulo $ 10^{9}+7 $ .
输入输出样例
输入样例 #1
2 4
11
输出样例 #1
14
输入样例 #2
10 100
1010101010
输出样例 #2
553403224