Boolean Function
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(xn,xn-1, ... ,x1).
The function can also be represented by its characteristic polynomial:
a0+a1x1+a2x2+a3x2x1+a4x3+a5x3x1+a6x3x2+a7x3x2x1+...+aNxnx_n-1...x1
Where the coefficients aJ in {0, 1}. The result of the evaluated polynomial modulo 2 is the value of our function.
For given n-dimensional function (its charactersitic polynomial),
count the number of vectors with exactly k 1s for which the function returns 1. Or in other words, the given polynomial evaluates to an odd number.
InputThe first line contains two integers n and k (1 <= k, n <= 20). The next line contains a string with $2^n$ characters representing the characteristic polynomial.
OutputPrint the number of n-dimensional vectors, with exactly k ones, for which the given function returns 1.
Input:
Output:
2 1
0111Output:
2Input:
Output:
4 2
1000000000000000Output:
6Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.