#1530 페인트 칠하기

75  1 s   128 MB  

Description

N개의 일렬로 배치된 타일과 P가지의 페인트가 있다.
N개의 타일에 각각 페인트를 칠하고 싶은데 인접한 타일끼리는 같은 색으로 칠하고 싶지 않다.
타일의 개수와 페인트의 종류가 주어질 때 타일을 칠하는 방법의 경우의 수를 구하는 프로그램을 작성하라.

Input

먼저 테스트 케이스의 수 T가 주어진다.
그 다음 T만큼 타일의 개수 N과 페인트의 종류 P가 주어진다.
( 1 <= T <= 100, 1 <= N <= 100, 1 <= P <= 1,000,000,000 )

Output

각 테스트 케이스마다 타일을 칠하는 방법의 경우의 수를 출력한다.
단 답이 1,000,000,007 이상이면 1,000,000,007로 나눈 나머지를 출력한다.

Sample Input

Sample Output

3
2 3
2 5
3 5
6
20
80

Source

From Arshuaz