비밀번호 공격자 (라지)

비밀번호는 현금인출기, 게시판 로그인, 휴대전화 잠금 해제, 출입문 개폐까지 곳곳에 쓰인다. 그래서 누구나 자기 비밀번호가 안전한지 신경 쓴다. 그러나 공격자는 언제나 비밀번호를 훔칠 방법을 찾아낸다. 다음은 그런 상황 하나다.

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

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

예를 들어 이브가 $M = 3$개의 키 3, 7, 5에서 지문을 찾았고 비밀번호가 $N = 4$글자라고 하자. 그러면 3577, 3557, 7353, 5735는 모두 가능한 비밀번호다. 이 넷 말고도 가능한 비밀번호가 32개 더 있다.

반면 다음은 가능하지 않다.

• 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 100$
• $1 \le M \le N \le 100$