Binary Polynomials

Every mapping $f$ from the set $\{0,1\}^n$ of $n$-dimensional binary vectors to $\{0,1\}$ is called a Boolean function of $n$ variables and is written $f(x_n, x_{n-1}, \ldots, x_1)$. Some properties of Boolean functions are of interest in cryptography. Let $B(n,k)$ denote the set of $n$-dimensional binary vectors that have exactly $k$ ones. For a given Boolean function $f$, the task is to find the number of vectors $(b_n, b_{n-1}, \ldots, b_1)$ from $B(n,k)$ such that $f(b_n, b_{n-1}, \ldots, b_1) = 1$.

The Boolean function is given by its (unique) polynomial modulo $2$. In these polynomials, addition and multiplication modulo $2$ are used, as defined in the tables of Fig. 1. In the polynomial of a function, any product of $m$ variables $x_{i_1} x_{i_2} \cdots x_{i_m}$ may or may not appear. So the general form of the polynomial for $n$ variables is:

$a_0 + a_1 x_1 + a_2 x_2 + a_3 x_2 x_1 + a_4 x_3 + a_5 x_3 x_1 + a_6 x_3 x_2 + a_7 x_3 x_2 x_1 + \cdots + a_N x_n x_{n-1} \cdots x_1$

where every coefficient $a_j$ (for $j = 0, 1, \ldots, N = 2^n - 1$) is $0$ or $1$. If a coefficient equals $0$ we omit the corresponding product, and if it equals $1$ we omit the coefficient itself. For example, the polynomial of the Boolean function "disjunction of 2 variables" shown in Fig. 2 is $0 + 1 \cdot x_1 + 1 \cdot x_2 + 1 \cdot x_2 x_1 = x_1 + x_2 + x_2 x_1$.

Fig. 1

Fig. 2

Your program must handle more than one test case. The first line of input contains the number $T$ of test cases. Each of the following $T$ lines describes one function: first the numbers $n$ and $k$ separated by a single space ($1 \le n \le 18$, $0 \le k \le n$), and then, separated by one more space, a string of $2^n$ zeros and ones giving the coefficients of the corresponding polynomial, ordered as in the general form above.

Output $T$ lines, each containing a single number: the number of vectors found for the corresponding function.