이진 다항식

$n$차원 이진 벡터의 집합 ${0,1}^n$에서 ${0,1}$로 가는 각 함수 $f$를 $n$변수 불 함수(Boolean function)라 하고 $f(x_n, x_{n-1}, \ldots, x_1)$로 나타낸다. 암호학에서는 불 함수의 몇 가지 성질이 중요하다. $B(n,k)$를 정확히 $k$개의 $1$을 가지는 $n$차원 이진 벡터들의 집합이라 하자. 주어진 불 함수 $f$에 대해, $B(n,k)$에 속하면서 $f(b_n, b_{n-1}, \ldots, b_1) = 1$을 만족하는 벡터 $(b_n, b_{n-1}, \ldots, b_1)$의 개수를 구하는 것이 문제이다.

불 함수는 그 (유일한) 2를 법으로 하는 다항식으로 주어진다. 이 다항식에서는 Fig. 1의 표에 정의된 대로 $2$를 법으로 하는 덧셈과 곱셈을 사용한다. 함수의 다항식에서 $m$개의 변수의 곱 $x_{i_1} x_{i_2} \cdots x_{i_m}$은 나타날 수도 있고 나타나지 않을 수도 있다. 따라서 $n$변수 다항식의 일반형은 다음과 같다.

$$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$$

여기서 모든 계수 $a_j$ ($j = 0, 1, \ldots, N = 2^n - 1$)는 $0$ 또는 $1$이다. 계수가 $0$이면 해당 곱을 생략하고, $1$이면 계수 자체를 생략한다. 예를 들어 Fig. 2에 주어진 "두 변수의 논리합(disjunction)" 불 함수의 다항식은 $0 + 1 \cdot x_1 + 1 \cdot x_2 + 1 \cdot x_2 x_1 = x_1 + x_2 + x_2 x_1$이다.

그림 1

그림 2

프로그램은 여러 개의 테스트 케이스를 처리할 수 있어야 한다. 입력의 첫째 줄에는 테스트 케이스의 개수 $T$가 주어진다. 다음 $T$개의 줄에는 각각 하나의 함수가 주어진다. 먼저 공백 하나로 구분된 두 수 $n$과 $k$ ($1 \le n \le 18$, $0 \le k \le n$)가 주어지고, 다시 공백 하나로 구분되어 위의 일반형 순서대로 나열된 다항식 계수인 $2^n$개의 $0$과 $1$로 이루어진 문자열이 주어진다.

$T$개의 줄을 출력하며, 각 줄에는 해당 함수에 대해 찾은 벡터의 개수를 하나의 수로 출력한다.