실행 시간 제한 | 메모리 제한 |
---|---|
1 초 | 128 MB |
농부인 준석이와 규민이는 각자가 가진 수많은 농장들을 하나로 연결하는 통로를 만들고자 합니다. 각각의 N개의 농장(1 <= N <= 100,000)에서 하나의 농장에서 다른 농장으로 하나씩 향하는 통로를 만들도록 약속했습니다.
즉, 총 N개의 통로를 만들게 됩니다. 준석이와 규민이는 각자 고용한 농부들에게 해당 작업을 지시했으나, 시간이 흘러 실제로 만들어진 통로는 M개(1 <= M < N)에 불과했습니다.
누구의 잘못인지를 파악하기 위해 준석이와 규민이는 개발자에게 문제를 의뢰합니다.
개발자인 당신은, 현재까지 만들어진 M개의 통로가 얼마나 많은 방법으로 만들어질 수 있는지 계산하고자 합니다. 예를 들어, 농장 3과 농장 4를 연결하는 통로가 이미 만들어져 있다면, 농장 3이 해당 통로를 만든 가능성과 농장 4가 길을 만든 가능성이 있습니다.
M개의 통로를 만들 수 있는 경우의 수를 계산하여 준석이와 규민이를 의뢰를 해결해주세요. 이 때 결과를 1,000,000,007로 나머지 연산한 값을 출력해야 합니다.
5 4 1 2 3 2 4 5 4 5
6
출처: USACO 2012 January Contest, Gold Division Problem 3. Bovine Alliance