Find the Number of Possible Ways for an Event
You are given three integers n, x, and y.
An event is being held for n performers. When a performer arrives, they are assigned to one of the x stages. All performers assigned to the same stage will perform together as a band, though some stages might remain empty.
After all performances are completed, the jury will award each band a score in the range [1, y].
Return the total number of possible ways the event can take place.
Since the answer may be very large, return it modulo 10^9 + 7.
Note that two events are considered to have been held differently if either of the following conditions is satisfied:
- Any performer is assigned a different stage.
- Any band is awarded a different score.
Example 1
Input
n = 1, x = 2, y = 3Output
6There are 2 ways to assign a stage to the performer, and the jury can award a score of 1, 2, or 3 to the only band.
Example 2
Input
n = 5, x = 2, y = 1Output
32Each performer will be assigned either stage 1 or stage 2, and all bands will be awarded a score of 1.
Constraints
- 1 <= n, x, y <= 1000