Watch 10 video solutions for Find the Number of Possible Ways for an Event, a hard level problem involving Math, Dynamic Programming, Combinatorics. This walkthrough by NeetCode has 384,140 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 109 + 7.
Note that two events are considered to have been held differently if either of the following conditions is satisfied:
Example 1:
Input: n = 1, x = 2, y = 3
Output: 6
Explanation:
Example 2:
Input: n = 5, x = 2, y = 1
Output: 32
Explanation:
Example 3:
Input: n = 3, x = 3, y = 4
Output: 684
Constraints:
1 <= n, x, y <= 1000