피보나치 문자열 부분 수열

이진 문자열 s가 주어진다(이 문자열의 각 문자는 0 또는 1이다).

문자열 t의 비용을 t에서 s가 등장하는 횟수라고 정의하자. 예를 들어 s가 11이고 t가 111011이면 t의 비용은 3이다.

또한 피보나치 문자열 수열을 다음과 같이 정의하자.

• F(0)은 0이다;
• F(1)은 1이다;
• i > 1이면 F(i) = F(i - 1) + F(i - 2)이며, 여기서 + 는 두 문자열의 이어 붙이기를 의미한다.

문자열 F(x)의 모든 부분 수열의 비용 합을 계산해야 한다. 답이 클 수 있으므로 109 + 7로 나눈 나머지를 계산한다.

첫 번째 줄에 두 정수 n와 x (1 ≤ n ≤ 100, 0 ≤ x ≤ 100)가 주어진다. 각각 s의 길이와 관심 있는 피보나치 문자열의 인덱스이다.

두 번째 줄에 n개의 문자로 이루어진 문자열 s가 주어진다. 각 문자는 0 또는 1이다.

문자열 F(x)의 모든 부분 수열의 비용 합을 109 + 7로 나눈 나머지를 유일한 정수로 출력한다.