비밀번호 공격자

비밀번호는 ATM, 온라인 포럼 로그인, 모바일 기기 잠금 해제, 출입문 개방 등 우리 생활에서 널리 사용된다. 모든 사람은 비밀번호 보안을 중요하게 생각한다. 그러나 공격자는 언제나 비밀번호를 훔칠 방법을 찾아낸다. 다음은 가능한 상황 중 하나이다.

공격자인 Eve가 피해자 Alice의 비밀번호를 훔치려 한다고 가정하자. Eve는 미리 키보드를 깨끗이 닦는다. Alice가 비밀번호를 입력하고 떠난 뒤, Eve는 키보드에 남은 지문을 수집한다. 이제 Eve는 비밀번호에 어떤 키가 사용되었는지 안다. 그러나 각 키가 몇 번 눌렸는지나 키 입력 순서는 알 수 없다.

문제를 단순화하기 위해, Eve가 Alice의 지문을 M개의 키에서만 발견한다고 가정하자. 또한 Eve는 다른 방법을 통해 Alice의 비밀번호가 N개의 문자로 이루어졌다는 것을 안다. 더 나아가 키보드의 각 키 입력은 서로 다른 단일 문자 하나만 생성한다. 또한 Alice는 '왼쪽', '홈', '백스페이스' 등과 같이 관련 없는 다른 키를 누르지 않는다.

다음은 예제이다. Eve가 M=3개의 키 '3', '7', '5'에서 Alice의 지문을 발견했고, Alice의 비밀번호 길이가 N=4자리라는 것을 안다고 가정하자. 그러면 다음 비밀번호는 모두 가능하다: 3577, 3557, 7353, 5735. (실제로는 가능한 비밀번호가 32개 더 있다.)

그러나 다음 비밀번호는 가능하지 않다.

1357  // There is no fingerprint on key '1'
3355  // There is fingerprint on key '7',
         so '7' must occur at least once.
357   // Eve knows the password must be a 4-digit number.

주어진 정보를 바탕으로 위 조건을 만족하는 가능한 비밀번호의 수를 구하라. 결과가 클 수 있으므로, 답을 1000000007($10^{9}$+7)로 나눈 나머지를 출력한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB.

작은 데이터 세트 (테스트 세트 1 - 공개)

T = 15. 1 ≤ M ≤ N ≤ 7.

큰 데이터 세트 (테스트 세트 2 - 비공개)

T = 100. 1 ≤ M ≤ N ≤ 100.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어지는 T개의 줄에는 각각 하나의 테스트 케이스를 나타내는, 공백으로 구분된 두 수 M과 N이 주어진다.

각 테스트 케이스마다 "Case #x: y"를 한 줄에 출력한다. 여기서 x는 테스트 케이스 번호이며 1부터 시작하고, y는 가능한 비밀번호의 총개수를 1000000007($10^{9}$+7)로 나눈 나머지이다.