UVA12983 The Battle of Chibi

曹操为进攻中国南方组建了一支庞大的军队，周瑜为此而忧心重重。他认为唯一能抵抗曹操的方法是在他的军队中安插间谍。但曹操手下的全体官兵都对他忠心耿耿，根本不可能策反其中之一。 所以周瑜只剩一种方法了：派个人假装投奔曹操。黄盖被选中执行此次关键任务。然而，曹操不轻易相信他人，所以黄盖必须为曹操泄露一些关键信息以获取信任。 周瑜和黄盖讨论后，按顺序拟定了 $N$ 条要泄露的信息。曹操估计每条信息都有 $a_i$ 的价值。 如果泄露的信息价值单调递增，则更能取得曹操的信任。所以黄盖决定按照顺序泄露价值单调递增的信息恰好 $M$ 条。换句话说，黄盖将会在不改变 $N$ 条信息顺序的情况下选择其中的 $M$ 条泄露出去。请计算出黄盖能做到这一点的方案数。

输入的第一行给出了测试数据的组数 $T$ $(1\le T\le100)$。 每组数据的第一行包含两个整数 $N$ $(1\le N\le10^3)$ 和 $M$ $(1\le M\le N)$，表示信息数量和黄盖将要选择的数量。接下来一行包含 $N$ 个整数 $a_i$ $(1\le a_i\le10^9)$，表示曹操估计的第 $i$ 条信息的价值。

对于每组数据，输出一行形如 `Case #x: y` 的信息。其中 $x$ 表示测试数据组数（从 $1$ 开始），$y$ 表示黄盖选择信息的方案数。 由于答案可能很大，你只需要输出答案对 $10^9+7$ 取模后的结果。

在第一组数据中，黄盖需要从 $3$ 条信息中挑选出 $2$ 条。由于序列已按升序排列因此它可以任意选择。 在第二组数据中，黄盖没有合法方案，因为任意 $2$ 条信息的权值都不递增。