You are given an array \(A\) consisting of \(N\) elements. Find the number of subsequences of length \(K\) with odd sum modulo \(10^9+7\).

Input format

The first line contains the number of test cases \(T\).
The first line of each test case contains two integers \(N\) denoting the number of elements in array \(A\) and \(K\) denoting the length of subsequence.
The second line of each test case contains \(N\) space-separated integers of array \(A\).

Output format

Print \(T\) lines. For each test case:

Print a single integer denoting the number of subsequences of length \(K\) with odd sum modulo \(10^9+7\).

Constraints

\(1 \leq T \leq 100\)
\(1 \leq N \leq 1000\)
\(1 \leq K \leq N\)
\(1 \leq A_i \leq 200\)
Sum of N over all test cases will not exceed 1000.