문제1530--페인트 칠하기

1530: 페인트 칠하기

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 257  통과: 85
[제출] [채점기록] [묻고답하기]

문제 설명

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

입력 설명

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

출력 설명

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

입력 예시 Copy

3
2 3
2 5
3 5

출력 예시 Copy

6
20
80

출처/분류