Given a binary number X of length M, which is XOR of N numbers, find out number of unique combinations of N binary numbers of length M such that their XOR is equal to X
. Two combinations are said to be different if there is at least one number which is in Combination 1 and not in Combination 2.
Input Format: The first line of standard input contains T , the number of test cases. For each test case, there will be 2 lines. First line of each test cases consists of 2 integers: N and M. Second line consists of number X
in binary number system.
Output Format: For each test case, print to standard output the number of unique combinations of N binary numbers whose XOR is equal to X.
EXAMPLE:
1
2 2
10
ans=4
Explanation
We need to find combination of all 2 numbers whose XOR will give the value 10.
The possible numbers are:
10 and 00
11 and 01
00 and 10
01 and 11
How can i solve this problem using dynamic programming?
Input Constraints:
1≤T≤10
1≤N≤10^5
1≤M≤10^5
Output Constraints:
Print the answer after applying modulo (%) operation with 10^9+7
Hint: writing XOR as $\oplus\,$, the operator is commutative, associative and nilpotent $A \oplus A = 0\,$, which implies that $A \oplus B=C \iff A=B \oplus C\,$.
For any $N-1$ arbitrary numbers $X_1,X_2,\cdots,X_{N-1}\,$ of length $M\,$, there exists one unique $X_N$ such that $X_1\oplus X_2 \oplus\cdots\oplus X_{N-1}\oplus X_N=X\,$, given by $X_N=X\oplus X_1 \oplus X_2 \oplus \cdots \oplus X_{N-1}\,$.