11224번 - Extensive Or 다국어

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 10⁹ + 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 10⁹ + 7.