#P1461. Binary Polynomials

Binary Polynomials

Description

Each mapping f of the set {0,1}

n

of n-dimensional binary vectors to {0,1} is called Boolean function of n variables and denoted by f(x

n

,x

n-1

,...,x1). For cryptography some properties of the Boolean functions are interesting. Let denote by B(n,k) the set of n-dimensional binary vectors that have k 1's. The task is for given Boolean function f to find the number of vectors (b

n

,b

n-1

,...,b1) from B(n,k) such that f(b

n

,b

n-1

,...,b1)=1.

The Boolean function will be given by its (unique) polynomial modulo 2. In these polynomials the operations addition and multiplication modulo 2 are used, defined as shown in the tables of Fig. 1. In the polynomial of a function any product of m variables could participate or not participate. So the general form of the polynomial for n variables is:
a0+a1x1+a2x2+a3x2x1+a4x3+a5x3x1+a6x3x2+a7x3x2x1+. . .+aNx<sub>n</sub><p>x</p><sub>n-1</sub><p>...x1
</p> where all coefficients aj, j=0,1,...,N=2^n-1, are 0's or 1's and if the coefficient is equal to 0 we will omit the corresponding product and if it is equal to 1 we just will omit the coefficient. For example, the polynomial of the Boolean function disjunction of 2 variables given on Fig. 2 is 0+1.x1+1.x2+1.x2x1=x1+x2+x2x1.
+01
001
110
*01
000
101
x1x2f
000
011
101
111

                                    fig.1                                                     fig.2

Input

Your program has to be ready to solve more than one test case. The first line of the input will contains only the number T of the test cases. Each of the following T lines will describe one function - first the numbers n and k separated by single space (1 <= n <= 18,0 <= k <= n) and then, separated by one more space a string of 2^n 0's and 1's that are the coefficients of the corresponding polynomial, ordered as in the general form of the polynomial given above.

Output

The output have to contain T lines with a single number each - the number of vectors found by your program.

3
2 1 0111
4 2 1000000000000000
5 3 00000000000000000000000000000001
2
6
0

Source

Southeastern Europe 2003