Given $N$ numbers and an integer $K$ find :

$(N^{maxmed}) mod 1e9+7$

Formally: we can define $maxmed$ as the maximum median of each subarray of length $K$.

Note that: the median of $K$ numbers indexed from $1$ is ${((K+1)/2)^{th}}$ smallest of them, rounding down for even $K$.

Input format

• The first line contains two integers $N$ and $K$ denoting the number of elements and size of the subarray.
• The second line contains $N$ space-separated integers.

Output format

Print the answer as described above.

Constraints

$2 \le N,K \le 10^5$

$1 \le a_i \le 10^5$

$K \le N$