시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 0 0 0 0.000%

문제

Consider a very large number R in a compressed format. It is compressed as a binary string s, and an integer k. Start with the empty string, and append s to it k times to get the binary representation of R. The string s is guaranteed to have a leading 1. Now, with R, solve the following problem: How many sets of n distinct integers are there such that each integer is between 0 and R −1, inclusive, and the XOR of all those integers is equal to zero? Since this number can get very large, return it modulo 109 + 7.

As a reminder, XOR is Exclusive Or. The XOR of two numbers is done bitwise. Using ⊕ for XOR:

  • 0 ⊕ 0 = 0
  • 0 ⊕ 1 = 1
  • 1 ⊕ 0 = 1
  • 1 ⊕ 1 = 0

XOR is associative, so a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c.

입력

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each input consists of exactly two lines. The first line has two space-separated integers n (3 ≤ n ≤ 7) and k (1 ≤ k ≤ 100 000), where n is the number of distinct integers in the sets, and k is the number of times to repeat the string s in order to build R. The second line contains only the string s, which will consist of at least 1 and at most 50 characters, each of which is either 0 or 1. s is guaranteed to begin with a 1.

출력

Output a single line with a single integer, indicating the number of sets of n distinct integers that can be formed, where each integer is between 0 and R − 1 inclusive, and the XOR of the n integers in each set is 0. Output this number modulo 109 + 7.

예제 입력

3 1
100

예제 출력

1

예제 입력 2

4 3
10

예제 출력 2

1978

예제 입력 3

5 100
1

예제 출력 3

598192244

힌트