A binary number X of length M is the XOR of some N numbers.

Write a program to find the number of unique arrays each containing N binary numbers of length M such that their XOR is equal to X .

Two arrays A and B are considered to be different if for at least 1 i where \( 1 \le i \le N \), \(A[i] \ne B[i]\)

Input format

• First line: T (number of test cases)
• First line in each test case: Two space-separated integers N and M
  
• Second line in each test case: X in binary

Output format

For each test case, print the number of unique combinations of M length N binary numbers whose XOR is equal to X.

As the output can be large, print it answer modulo \(10^9+7\).

Constraints

\(1 \le T \le 10 \)
\(1 \le N \le 10^5 \)
\(1 \le M \le 10^5 \)