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.