Бінарні поліноми
Кожне відображення 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 рядків, кожен з одним числом - кількість векторів, знайдених вашою програмою.