시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB34181352.000%

문제

영선이는 유명한 온라인 프로그래밍 대회 "선데이 코딩"에 참가하려고 한다.

대회가 진행되는 동안 참가자는 R개의 방으로 나누어져 있으며, 각 방에는 참가자 S명이 들어가있다. 즉, 참가자의 수는 R*S명이다. 방은 1번부터 R번까지 번호가 매겨져 있다.

대회에 동점자는 없기 때문에, 대회가 끝난 후에 각 참가자는 1등(우승)부터 R*S등까지 등수를 받게 된다.

방 우승자는 각각의 방에서 등수가 가장 좋은 사람을 의미한다.

영선이는 대회가 끝난 후에 각 방의 우승자의 등수를 적은 수열을 만들었다. 수열의 i번째 수는 i번 방의 우승자의 등수를 의미한다.

R과 S가 주어졌을 때, 만들 수 있는 서로 다른 수열의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 R과 S가 주어진다. (1 ≤ R, S ≤ 100)

출력

첫째 줄에 만들 수 있는 서로 다른 수열의 개수를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

2 1

예제 출력 1

2

예제 입력 2

1 2

예제 출력 2

1

예제 입력 3

2 2

예제 출력 3

4

예제 입력 4

4 5

예제 출력 4

6840

힌트

예제 1의 경우에 방이 2개, 각 방마다 참가자는 1명이다. 즉, 수열은 (1, 2), (2, 1)이 될 수 있다.

예제 3의 경우에는 방이 2개, 각 방마다 참가자는 2명이다. 만들 수 있는 수열은 (1, 2), (2, 1), (1, 3), (3, 1) 이다. 이때, (2, 3)과 (1, 4)는 절대로 만들 수 없는 수열이다.

출처