有 $n$ 个编号为 $1$ 到 $n$ 的小球和一个双端队列。你需要将这些小球依次放入双端队列中。在第 $i$ 轮中，你需要将编号为 $p_i$ 的小球放入双端队列。每个小球都有等概率（即各 $1/2$ 的概率）被插入到双端队列的左端或右端。

设序列 $(x_1, x_2, \dots, x_n)$ 为双端队列中从左到右的小球编号。双端队列的美丽度 $B(x_1, x_2, \dots, x_n)$ 定义如下：

$$B(x_1, x_2, \dots, x_n) = \left(\sum_{i=1}^{n-1} [x_i > x_{i+1}]\right)^k$$

其中 $k$ 是给定的常数。注意，若条件成立，则 $[\text{condition}] = 1$，否则为 $0$。

你需要求出 $B(x_1, x_2, \dots, x_n)$ 的期望值。

输入格式

输入包含多组测试数据。对于每组测试数据：

第一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 1000, 1 \le k \le 50$)，分别表示小球的数量和给定的常数。

第二行包含 $n$ 个互不相同的整数：$p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$)。

所有测试数据的 $n$ 之和不超过 $1000$。

输出格式

对于每组测试数据，设期望值为 $E$，你需要输出 $E \cdot 2^n \bmod (10^9 + 7)$ 的值。

样例

样例输入 1

1 3
1
2 3
1 2
3 3
1 2 3

样例输出 1

0
2
20