wizardrabbit   3년 전

* 본 지문은 12198번 문제를 번역 및 재구성하여 작성했습니다.

* 이 문제는 12199번 문제와 제한조건을 제외하고 완전히 동일한 문제입니다.

문제


해커 이브는 앨리스의 컴퓨터 비밀번호를 알고 싶어한다. 이브는 두 가지 정보를 알고 있는데, 바로 비밀번호에 사용된 문자의 종류가 $M$ 종류라는 것과 비밀번호가 총 $N$ 자리라는 것이다.

이브를 위해 가능한 비밀번호가 총 몇 가지인지 알려주는 프로그램을 작성해 보자.

입력


입력은 여러 개의 테스트 케이스로 이루어져 있다.

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

이후 $T$ 개의 줄에 걸쳐 $T$ 개의 테스트 케이스가 주어진다. 각 테스트 케이스에서는 $M$ 과 $N$ 이 공백 한 칸을 사이에 두고 차례대로 주어진다.

출력


각 테스트 케이스마다, 한 줄에 하나씩 가능한 비밀번호가 몇 가지인지를 출력한다. 단, 답이 매우 커질 수 있으므로 $10^9 + 7$ 로 나눈 나머지를 대신 출력하자.

답을 출력할 때는 아래의 형식대로 출력한다. $x$ 는 몇 번째 테스트 케이스인지를 의미하고, $y$ 는 문제에서 요구하는 답을 의미한다.

Case #x: y

제한


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

댓글을 작성하려면 로그인해야 합니다.