6400: 赤壁之战

内存限制:256 MB 时间限制:2 S
题面:传统 评测方式:文本比较 上传者:
提交:2 通过:2

题目描述

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

输入格式

输入格式

第一行包含整数 T,表示共有 T 组测试数据。

每组数据,第一行包含两个整数 N 和 M

第二行包含N 个整数,表示完整的序列 A

输出格式

输出格式

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

输出格式为 Case #x: y,x 为数据组别序号,从 1 开始,y 为结果。

由于答案可能很大,请你输出对 109+7 取模后的结果。

数据范围

1≤T≤100,
1≤M≤N≤1000,
∑Ni×Mi≤107
序列中的整数的绝对值不超过109

输入样例 复制

2
3 2
1 2 3
3 2
3 2 1

输出样例 复制

Case #1: 3
Case #2: 0