Password Attacker (Small)

Passwords are everywhere in daily life: cash machines, forum logins, phone unlocking, door entry. Everyone cares whether a password is safe, and attackers keep finding ways to steal one. Here is one such situation.

Eve, the attacker, wants Alice's password. Eve wipes the keyboard clean in advance. After Alice types the password and leaves, Eve collects the fingerprints left on the keyboard. Eve now knows which keys the password uses. She does not learn how many times each key was pressed, and she does not learn the order of the keystrokes.

To keep the problem simple, assume the fingerprints Eve finds sit on exactly $M$ keys. Assume also that Eve knows from another source that Alice's password is $N$ characters long. Each keystroke produces exactly one character, and Alice presses no other keys such as left, home, or backspace.

A possible password is therefore a string of length $N$ built only from the $M$ marked keys, in which each of the $M$ keys appears at least once.

For example, suppose Eve finds fingerprints on the three keys '3', '7', and '5' ($M=3$) and the password has four characters ($N=4$). Then 3577, 3557, 7353, and 5735 are all possible, and there are 36 possible passwords in total. On the other hand 1357 is impossible because key '1' carries no fingerprint. 3355 is impossible because '7' carries a fingerprint and never appears. 357 is impossible because its length is not 4.

Count the possible passwords and report the count 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 a space, describing one test case.

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

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