Бинарные многочлены
Каждое отображение f множества {0,1}^n n-мерных бинарных векторов в {0,1} называется булевой функцией n переменных и обозначается как f(x_n,x_{n-1},...,x_1). В криптографии интерес представляют определенные свойства булевых функций. Обозначим через B(n,k) множество n-мерных бинарных векторов, содержащих ровно k единиц. Задача заключается в том, чтобы для данной булевой функции f определить количество векторов (b_n,b_{n-1},...,b_1) из B(n,k), для которых f(b_n,b_{n-1},...,b_1)=1.
Булева функция задается своим (уникальным) полиномом по модулю 2. В этих полиномах используются операции сложения и умножения по модулю 2, определенные как показано в таблицах на Рис. 1. В полиноме функции любое произведение из m переменных x_i1 x_i2 ... x_im может присутствовать или отсутствовать. Таким образом, общая форма полинома для n переменных выглядит следующим образом:
a_0+a_1x_1+a_2x_2+a_3x_2x_1+a_4x_3+a_5x_3x_1+a_6x_3x_2+a_7x_3x_2x_1+. . .+a_nx_nx_{n-1...}x_1
где все коэффициенты a_j, j=0,1,...,N=2^n-1, равны 0 или 1. Если коэффициент равен 0, соответствующее произведение опускается, а если он равен 1, коэффициент просто не пишется. Например, полином булевой функции дизъюнкции 2 переменных, представленный на Рис. 2, записывается как 0+1.x_1+1.x_2+1.x_2x_1=x_1+x_2+x_2x_1.
Входные данные
Ваша программа должна быть готова обрабатывать несколько тестовых случаев. Первая строка входного файла содержит число T — количество тестовых случаев. Каждая из следующих T строк описывает одну функцию: сначала идут числа n и k, разделенные пробелом (1 ≤ n ≤ 18, 0 ≤ k ≤ n), а затем, через пробел, строка из 2^n символов 0 и 1, которые являются коэффициентами соответствующего полинома, упорядоченными в соответствии с общей формой полинома, приведенной выше.
Выходные данные
Выходной файл должен содержать T строк, каждая из которых содержит одно число — количество векторов, найденных вашей программой.