비밀번호 공격자 (작은 문제)

비밀번호는 현금인출기, 온라인 게시판 로그인, 휴대전화 잠금 해제, 출입문 등 생활 곳곳에서 쓴다. 그래서 누구나 비밀번호가 안전한지 신경 쓴다. 그런데도 공격자는 늘 비밀번호를 빼낼 방법을 찾아낸다. 아래는 그런 상황 하나다.

공격자 이브는 앨리스의 비밀번호를 알아내려 한다. 이브는 미리 키보드를 깨끗이 닦아 둔다. 앨리스가 비밀번호를 입력하고 자리를 뜨면, 이브는 키보드에 남은 지문을 모은다. 이제 이브는 비밀번호에 어떤 키가 쓰였는지 안다. 다만 각 키를 몇 번 눌렀는지, 어떤 순서로 눌렀는지는 알아내지 못한다.

문제를 간단히 하기 위해, 이브가 찾은 지문이 정확히 $M$개의 키에만 남아 있다고 하자. 또 이브는 다른 경로로 앨리스의 비밀번호가 $N$글자라는 사실을 안다. 키를 한 번 누르면 문자가 정확히 하나 입력되고, 앨리스는 left, home, backspace 같은 다른 키는 누르지 않는다.

따라서 가능한 비밀번호는 지문이 남은 $M$개의 키만 써서 만든 길이 $N$짜리 문자열 중에서, $M$개의 키가 모두 한 번 이상 나오는 것이다.

예를 들어 이브가 '3', '7', '5' 세 키($M=3$)에서 지문을 찾았고 비밀번호가 네 글자($N=4$)라고 하자. 3577, 3557, 7353, 5735는 모두 가능하며, 가능한 비밀번호는 전부 36개다. 반대로 1357은 '1'에 지문이 없으므로 불가능하다. 3355는 '7'에 지문이 있는데 '7'이 한 번도 나오지 않으므로 불가능하다. 357은 길이가 4가 아니므로 불가능하다.

가능한 비밀번호의 개수를 세어 $10^9+7$로 나눈 나머지를 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

다음 $T$개의 줄에는 각각 테스트 케이스 하나를 나타내는 두 정수 $M$과 $N$이 공백으로 구분되어 주어진다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 가능한 비밀번호의 개수를 $10^9+7$로 나눈 나머지다.

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