P16482 [GKS 2014 #B] Password Attacker

密码在我们的生活中被广泛使用：用于 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$ 个其他可能的密码。） 然而，以下这些密码是不可能的： | 密码示例 | 原因 | |:-:|:---| | 1357 | 按键 '1' 上没有指纹 | | 3355 | 按键 '7' 上有指纹，因此 '7' 必须至少出现一次。 | | 357 | Eve 知道密码必须是一个 4 位数字。 | 根据这些信息，请统计共有多少个可能的密码满足上述条件。由于结果可能很大，请输出答案对 $10^9+7$ 取模后的值。

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

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

### 限制 **小数据集（测试集 1 - 可见）** $T = 15$ $1 \le M \le N \le 7$ **大数据集（测试集 2 - 隐藏）** $T = 100$ $1 \le M \le N \le 100$ 翻译由 DeepSeek V4 Pro 完成