Extensive Or

시간 제한3초메모리 제한256 MB

요약

문자열 s를 k번 이어 붙인 이진수보다 작은 수 중에서 xor이 0이 되는 n원소 부분집합 개수를 1e9+7로 나눈 나머지를 구합니다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 조합론, 비트 연산
정답자: 아직 제출이 없습니다

문제

매우 큰 수 $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$ 로 나눈 나머지를 한 줄에 출력한다.

예제3

예제 1
입력
```
3 1
100
```
예상 출력
```
1
```
예제 2
입력
```
4 3
10
```
예상 출력
```
1978
```
예제 3
입력
```
5 100
1
```
예상 출력
```
598192244
```