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.