Informatica Online Judge

  Color prob for illust (Small) [0714 / 02CA]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 40   Total Tried : 50


The Champion of this Problem (C++) : gs14049 - 0ms / 123byte
My Best Submission (C++) : N/A

[]

Background

최근 teram은 수채화를 그리시는 어머니를 보고, 자신은 일러스트를 배워보고 싶다는 욕심이 생겼다.
하지만 얼마 지나지 않아 teram은 좌절하였다. 18년 동안 미술과는 담을 쌓아둔 채 인생을 살아온 그에게는 선 따기나 채색은 커녕 밑그림을 그리는 것 조차 버거웠던 것이었다.

그리하여 teram은 교내에서 ‘일러스트레이션의 마술사’라고 불리는 량이를 찾아갔다.
하지만 teram으로부터 사정을 들은 량이는 갑자기 n개의 구간으로 나뉘어진 원판과 k개의 물감을 가져오는 것이었다.
그리고는 teram에게 다음과 같이 말하였다.

“여기 n개의 구간으로 나뉘어진 원판이 있어. 이웃한 구간끼리는 같은 색을 칠하지 않되, k개의 물감으로 구간을 모두 칠하는 경우의 수를 10억 7로 나눈 나머지는 얼마일까? 내가 n, k값을 줄 테니 1초만에 대답하면 일러스트에 대해서 가르쳐 줄게.”

그 말을 들은 teram은 눈앞이 깜깜해졌다! 안 그래도 수학에서 조합 파트가 제일 자신 없는 데 관련 문제를 1초만에 답하라고 하다니!! 게다가 그 값을 10억 7로 나누라니!!!
teram이 량이에게 무사히 일러스트를 배울 수 있도록 도와주자.

예를 들어서 n=4, k=3 이라면 다음과 같이



총 18가지의 색을 칠하는 방법이 있다.
(k개의 색을 모두 사용할 필요는 없으며, 원순열은 무시한다. 즉, 돌려서 형태가 동일한 경우는 모두 다른 것으로 취급한다.)

Input

첫째 줄에 원판을 나누는 구간의 개수 n과 색의 종류 k가 공백으로 구분되어 입력된다.
1<=n,k<=5,000 이다.

Output

원판을 칠하는 경우의 수를 1,000,000,007 (10억 7) 로 나눈 나머지를 출력한다.

IO Example

입력
4 3

출력
18

문제 출제 및 데이터 작성 : 경남과학고(GSHS) 27th 오평석(teram)
Special Thanks to GSHS 27.5th 정기량(량이)

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]