该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

Susan 刚刚完成了一组文件的文书工作，这些文件仍然堆在她的桌子上。它们有序列号，当她的老板带来时，它们是按顺序堆叠的。然而，由于她太懒了，没有将滑出堆的文件放回正确的位置，现在的顺序并不完整。 在她已经完成了工作后，老板希望她立即将文件放回他发送的文件盒。当然，文件应按其序列号的顺序存放在盒子中。

桌子上刚好有足够的空间来放置两个临时文件堆，Susan 计划在这两个临时堆中存放文件。当前堆中的所有文件将逐个从顶部移动到这两个临时堆中的一个，由于初始堆是按高会变低的顺序倒塌，因此应在临时堆中放置过多的文件。将所有文件移到两个临时堆中后，将这两个临时堆的顶端将文件移到盒子中。为了允许按顺序将文件移动到盒子中，两临时堆中的文件应按其序列号的逆序排列。

例如，假设堆中有六个文件，按从上到下的顺序为 1、3、4、2、6 和 5，并且临时堆中最多只能放置三个文件。 那么，她可以形成两个临时堆，分别为从上到下依次为 5、2 和 1（见图片）。两个临时堆都是逆序排列的。然后，比较两个临时堆顶部的文件序列号，较小的文件（在这种情况下是 6）将首先被移除并放入文件盒中。重重复此过程，所有文件将按文件盒中完美排序。

Susan 想知道这个计划是否是可行的，如果可行，有多少种不同的方式可以将文件堆到两个临时堆中。你需要通过编写一个程序来计算不同的方式数量来帮助 Susan，如果计划不可行，则输出 0。

由于堆中的每个文件可以移动到两个临时堆中的任何一个，对于一个文件，总共有 $2^n$ 种不同的选择组合，但其中一些可能会导致临时堆的逆序排列，因此是不合法的。

上述示例对应于样例输入 1 的第一个案例。在这种情况下，最后两个文件 5 和 6 可以交换它们的目的地。此外，完全交换两个临时堆的角色也是可以的。由于任何其他移动方案都将导致其中一个堆超过三个文件或使堆失去逆序，因此在这种情况下，将文件堆到临时堆的不同方式的总数为 $2 \times 2 = 4$。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$，其中：

• $n$ 是堆中的文件数量 $(1 \le n \le 5000)$；
• $m$ 是一个临时堆中可以堆叠的文件数量，而不会使其倒塌的风险（$2 \le m \le n$）。

接下来的一行包含数字 $s_1$ 到 $s_n$；这些数字是文件堆中文件的序列号，从顶部到底部。保证所有数字 $1$ 到 $n$ 恰好出现一次。

输出格式

输出一个整数，表示形成两个适合目标临时堆的方式的数量。 如果没有可行的选择，则输出 0。 输出方式数量对 $10^9 + 7$ 取模的结果。

输入输出样例

6 3
1 3 4 2 6 5

4

6 6
1 3 4 2 6 5

8

4 4
4 3 1 2

0