SP28599 BDOI16C - Counting Magical Permutatitons

**联合国** 在遥远的星球上，有一个迷人的国度，名叫魔法国。那里的孩子们热衷于参与各种有趣的数字游戏，其中一个热门的游戏叫做「逆序对」。在这个游戏中，会给出从 1 到 $N$ 的一组数字，以某种固定顺序排列。你的任务是计算这个排列中所有的逆序对。第一个正确说出逆序对数量的人将获胜。 逆序对的定义是：如果存在一对索引 $i$ 和 $j$ 满足 $i < j$ 且第 $i$ 个位置的数字大于第 $j$ 个位置的数字，即构成一个逆序对。 例如，考虑数字 1 到 5 的排列：5, 1, 4, 2, 3。这个排列产生了以下逆序对：(5, 1)、(5, 4)、(5, 2)、(5, 3)、(4, 2)、(4, 3)，因此逆序对总数为 6。最早说出这个数字的人便胜出。 对于本问题，我们想知道对于数字 1 到 $N$ 的排列中，有多少种情况至少包含 $K$ 个逆序对。 如果两个排列中，存在某个位置 $i (1 \le i \le N)$ 的数字不相同，则这两个排列就被视为不同的排列。

输入的第一行包含一个整数 $T (1 \le T \le 50)$，表示测试用例的数量。接下来的每个测试用例占据一行，包含两个整数：$N$ 和 $K$。

对于每一个测试用例，输出格式为 `Case x: y`，其中 $x$ 是测试用例编号，$y$ 是至少包含 $K$ 个逆序对的排列的数量。由于这个数量可能相当大，需要输出 $y$ 模 10,007 的结果。

- 简单版本：$1 \le N \le 200$ 且 $0 \le K \le 300$。 - 困难版本：$1 \le N \le 2000$ 且 $0 \le K \le 3000$。 ### 样例输入 ``` 3 3 1 2 1 3 2 ``` ### 样例输出 ``` Case 1: 5 Case 2: 1 Case 3: 3 ``` **题目设置者：Anindya Das** **本翻译由 AI 自动生成**