Extensive Or

매우 큰 수 $R$이 압축된 형태로 주어진다. 압축 결과는 이진 문자열 $s$와 정수 $k$이다. 빈 문자열에서 시작해 $s$를 $k$번 이어 붙이면 $R$의 이진 표현이 된다. $s$의 첫 글자는 항상 1이다.

이렇게 정해진 $R$에 대해 다음을 구한다. 0 이상 $R - 1$ 이하의 서로 다른 정수 $n$개로 이루어진 집합 중에서, 원소 전체의 XOR가 0인 집합은 몇 개인가? 답이 매우 커질 수 있으므로 $10^9 + 7$로 나눈 나머지를 구한다.

XOR는 배타적 논리합이고, 두 수의 XOR는 비트 단위로 계산한다. XOR를 $\oplus$로 쓰면 다음과 같다.

• $0 \oplus 0 = 0$
• $0 \oplus 1 = 1$
• $1 \oplus 0 = 1$
• $1 \oplus 1 = 0$

XOR는 결합법칙이 성립하므로 $a \oplus (b \oplus c) = (a \oplus b) \oplus c$이다.

입력은 테스트 케이스 하나로 이루어지고 정확히 두 줄이다. 첫째 줄에 정수 $n$과 $k$가 공백을 사이에 두고 주어진다 ($3 \le n \le 7$, $1 \le k \le 100000$). $n$은 집합에 들어가는 서로 다른 정수의 개수이고, $k$는 $R$을 만들려고 $s$를 이어 붙이는 횟수이다. 둘째 줄에 문자열 $s$가 주어진다. $s$의 길이는 1 이상 50 이하이고 각 문자는 0 또는 1이며, 첫 글자는 1이다.

0 이상 $R - 1$ 이하의 서로 다른 정수 $n$개로 이루어지고 원소 전체의 XOR가 0인 집합의 개수를 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.