Password Attacker (Large)

Passwords are everywhere: cash machines, forum logins, phone unlock screens, door locks. Everyone cares whether a password is safe, and attackers keep finding ways to steal one. Here is one such situation.

Eve wants to steal Alice's password. Eve wipes the keyboard clean beforehand. After Alice types her password and walks away, Eve collects the fingerprints left on the keys. Eve now knows which keys the password uses. She does not know how many times each key was pressed, and she does not know the order of the keystrokes.

To keep the problem simple, assume Eve finds fingerprints on exactly $M$ keys, and that she learned by another route that Alice's password is $N$ characters long. One keypress produces one character, different keys produce different characters, and Alice never presses keys such as left, home or backspace.

For example, suppose Eve finds fingerprints on the $M = 3$ keys 3, 7 and 5, and the password is $N = 4$ characters long. Then 3577, 3557, 7353 and 5735 are all possible passwords. Besides those four, 32 more passwords are possible.

These are not possible:

• 1357, because key 1 carries no fingerprint.
• 3355, because key 7 carries a fingerprint, so 7 has to appear at least once.
• 357, because the password is 4 characters long.

Count how many passwords fit what Eve knows. The count can be large, so print it modulo $10^9 + 7$.

The first line contains the number of test cases, $T$.

Each of the next $T$ lines contains two integers $M$ and $N$ separated by one space.

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the number of possible passwords modulo $10^9 + 7$.

• $1 \le T \le 100$
• $1 \le M \le N \le 100$