题目描述

密码在我们的生活中被广泛使用：用于 ATM 机、在线论坛登录、手机解锁以及门禁系统。每个人都关心密码的安全性。然而，攻击者总能找到方法窃取我们的密码。以下是一种可能的情形：

假设攻击者 Eve 想要窃取受害者 Alice 的密码。Eve 事先清洁了键盘。在 Alice 键入密码并离开后，Eve 收集键盘上的指纹。现在，她知道了密码中使用了哪些按键。但是，Eve 无从得知每个按键被按下了多少次，也无从得知按键序列的顺序。

为了简化问题，假设 Eve 发现 Alice 的指纹只出现在 $M$ 个按键上。同时，她通过其他途径得知，Alice 的密码包含 $N$ 个字符。此外，键盘上的每一次击键只会产生一个单一且唯一的字符。而且，Alice 不会按下其他无关的按键，例如“左箭头”、“Home”、“退格”等。

这里有一个例子。假设 Eve 在 $M=3$ 个按键 '3'、'7' 和 '5' 上发现了 Alice 的指纹，并且她知道 Alice 的密码长度为 $N=4$ 位。那么，以下所有密码都是可能的：$3577$、$3557$、$7353$ 和 $5735$。（事实上，还有 $32$ 个其他可能的密码。）

然而，以下这些密码是不可能的：

根据这些信息，请统计共有多少个可能的密码满足上述条件。由于结果可能很大，请输出答案对 $10^9+7$ 取模后的值。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来的 $T$ 行，每行包含两个用空格分隔的整数 $M$ 和 $N$，表示一个测试用例。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是可能的密码总数对 $10^9+7$ 取模的结果。

4
1 1
3 4
5 5
15 15

Case #1: 1
Case #2: 36
Case #3: 120
Case #4: 674358851

提示

限制

小数据集（测试集 1 - 可见）

$T = 15$

$1 \le M \le N \le 7$

大数据集（测试集 2 - 隐藏）

$T = 100$

$1 \le M \le N \le 100$

翻译由 DeepSeek V4 Pro 完成