57. Arrange the King's Army

Difficulty: medium · Dynamic Programming, Math

Problem

A king lines up `N` soldiers. Each position gets a soldier of some rank from `1` to `R`. The arrangement must satisfy: - the first soldier has rank `1`, - the last soldier has rank `END`, - no two adjacent soldiers have the same rank. Count the valid arrangements. Because the count can be huge, print it modulo `10^9 + 7`. For example, with `N = 3`, `R = 3`, `END = 2` the only valid arrangement is `[1, 3, 2]`.

Input

- Line 1: the integer `N`. - Line 2: the integer `R`. - Line 3: the integer `END`.

Output

Print the number of valid arrangements modulo `1000000007`.

Example 1

Input:
3
3
2
Output:
1

Explanation: The middle soldier must differ from 1 and from 2, so it can only be 3: [1, 3, 2].

Example 2

Input:
4
3
1
Output:
2

Explanation: The valid lines are [1,2,3,1] and [1,3,2,1], so the answer is 2.

Example 3

Input:
2
5
1
Output:
0

Explanation: With only two soldiers, the second would have rank 1 next to rank 1, which is not allowed: 0.

Constraints

- 1 <= N <= 10^5 - 1 <= R <= 10^9 - 1 <= END <= R

Solutions are judged against 3 sample and 11 hidden tests. Sign in to solve it · All problems