题目描述

给定一个长度为$\red N$的序列$\red A$，求$\red A$有多少个长度为$\red M$的严格递增子序列。

输入格式

第一行包含整数$\red T$，表示共有$\red T$组测试数据。

每组数据，第一行包含两个整数$\red N$和$\red M$。

第二行包含$\red N$个整数，表示完整的序列$\red A$。

输出格式

每组数据输出一个结果，每个结果占一行。

输出格式为$\red {“Case \#x: y”}$，$\red x$为数据组别序号，从$\red 1$开始，$\red y$为结果。

由于数据可能很大，请你输入对$\red {10 ^9 +7}$取模后的结果。

样例

输入样例

2
3 2
1 2 3
3 2
3 2 1

输出样例

Case #1: 3
Case #2: 0

提示

$\red {1≤T≤100}$,

$\red {1≤M≤N≤1000}$,

序列中的整数的绝对值不超过$\red {10 ^9}$ 。