Susan 擅长整理餐桌，但并不擅长整理办公桌。

Susan 刚刚处理完一堆文件，这些文件现在仍然堆在她的桌子上。它们有各自的序列号，当老板把它们拿来时，它们是按顺序堆放的。然而，现在的顺序并不完美，因为她太懒了，没有把滑出堆的文件放回正确的位置。老板听说她处理完了，想要她立即把文件放进他送来的文件盒里。当然，文件应该按序列号的顺序存放在盒子里。

桌子上有足够的空间再放两个文件堆，Susan 计划在那里建立两个临时堆。当前堆中的所有文件都要从顶部开始，一个接一个地移动到两个临时堆中的任意一个。由于匆忙中把这些堆叠得太高会导致它们倒塌，因此不能在上面放置太多的文件。在将所有文件移动到临时堆并收到文件盒后，两个堆中的文件将从顶部开始，一个接一个地移入盒中。为了能按顺序移入盒子，两个堆中的文件必须按序列号的降序排列。

例如，假设堆中有六个文件，从顶部到底部依次为 1, 3, 4, 2, 6, 5，并且临时堆最多只能容纳三个文件。那么，她可以形成两个临时堆，一个从顶部开始依次为 6, 4, 3，另一个为 5, 2, 1（见图）。两个临时堆都是降序排列的。然后，比较两个临时堆顶部文件的序列号，将较大的一个（本例中为 6）移除并首先放入文件盒。重复此过程，所有文件都将完美地按顺序存放在文件盒中。

Susan 想知道对于当前堆中的文件，这个计划是否可行，如果可行，有多少种不同的堆叠方式。请你编写一个程序来计算不同方式的数量，如果计划不可行，则应输出 0。

由于堆中的每个文件都可以移动到两个临时堆中的任意一个，对于 $n$ 个文件，总共有 $2^n$ 种组合方式，但其中一些可能会破坏临时堆的降序排列，因此是不合适的。

上述例子对应于样例输入的第一种情况。在这种情况下，最后两个文件 5 和 6 可以交换它们的目的地。此外，交换两个临时堆的角色也是完全可以的。由于任何其他移动序列都会使其中一个堆的高度超过 3 和/或使其顺序混乱，因此在这个例子中，将文件堆叠到临时堆的不同方式总数为 $2 \times 2 = 4$。

输入格式

第一行包含两个整数 $n$ 和 $m$。其中 $n$ 是堆中的文件数量 ($1 \le n \le 5000$)，$m$ 是一个临时堆在不冒倒塌风险的情况下可以堆叠的文件数量 ($n/2 \le m \le n$)。下一行包含数字 $s_1$ 到 $s_n$；这些数字是文件堆中从顶部到底部的序列号。保证所有 1 到 $n$ 的数字恰好出现一次。

输出格式

输出一行，包含一个整数，表示符合目标要求的形成两个临时堆的方法数。

如果没有任何选择可行，方法数自然为 0。如果可能的方法数大于或等于 $10^9 + 7$，则输出方法数对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

6 3
1 3 4 2 6 5

样例输出 1

4

样例输入 2

6 6
1 3 4 2 6 5

样例输出 2

8

样例输入 3

4 4
4 3 1 2

样例输出 3

0