|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|3 초||256 MB||2||1||1||100.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:
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
4 3 10
5 100 1