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 <= 1000Problem Overview: You have n participants, x available stages, and y possible score values for each stage. Participants are distributed across stages such that every used stage has at least one participant. Each used stage then receives one of the y score values. The task is to count the total number of valid configurations modulo 1e9+7.
The key observation: if exactly k stages are used, three independent choices happen. First distribute n participants into k non‑empty groups. Then map those groups to k distinct stages out of x. Finally assign a score to each used stage. Summing this count for all valid k gives the final answer.
Approach 1: Combinatorial Counting with Stirling Numbers (Time: O(n * min(n,x)), Space: O(n * min(n,x)))
This approach models the distribution of participants using Stirling numbers of the second kind. S(n, k) represents the number of ways to partition n items into k non‑empty groups. Once groups are formed, map them to k distinct stages using permutations P(x, k). Each used stage independently chooses a score from y possibilities, giving y^k choices. The total for a fixed k becomes S(n,k) * P(x,k) * y^k. Iterate k from 1 to min(n, x), accumulate the values modulo 1e9+7. This method relies heavily on combinatorics and factorial-based permutations.
Approach 2: Dynamic Programming for Stirling Numbers (Time: O(n * min(n,x)), Space: O(n * min(n,x)))
Instead of using a direct combinatorial formula, compute S(n,k) using the recurrence S(n,k) = S(n-1,k-1) + k * S(n-1,k). Build a DP table where rows represent participants and columns represent group counts. Each state represents how many ways participants can form k non‑empty groups. After computing the DP table, combine each S(n,k) with the permutation term P(x,k) and the scoring term y^k. Modular exponentiation handles the y^k factor efficiently. This formulation fits naturally with dynamic programming and avoids needing precomputed Stirling values.
Recommended for interviews: The combinatorial formulation with Stirling numbers is what interviewers usually expect for a hard counting problem involving labeled resources and non‑empty partitions. Showing the DP recurrence for S(n,k) demonstrates deeper understanding of math and combinatorial identities. Brute enumeration is infeasible due to exponential growth, so recognizing the partition‑then‑assign structure is the real insight.
This approach focuses on understanding the number of ways performers can be assigned to different stages and the number of scoring possibilities for the bands. We calculate the number of ways to assign performers to stages as x^n and multiply it by the number of scoring combinations for each band, which is y^x. Finally, result modulo 10^9 + 7 is returned.
This C solution computes the number of ways to assign performers to stages using power_mod, which calculates base^exp % mod. The final result is derived by multiplying the number of stage assignments and scoring combinations, then taking the modulus.
Time Complexity: O(log n + log x) due to modular exponentiation.
Space Complexity: O(1).
This approach utilizes dynamic programming to calculate the number of ways to assign performers to stages while also keeping track of scored bands. The idea is to build up a solution incrementally using previously computed results, which can be especially useful in cases where recursive approaches might lead to computation of the same sub-problems.
This C solution uses a dynamic programming array to keep track of ways performers can be assigned to stages. It iteratively fills this array, using previously computed values to build the solution dynamically.
Time Complexity: O(n + x)
Space Complexity: O(n).
We define f[i][j] to represent the number of ways to arrange the first i performers into j programs. Initially, f[0][0] = 1, and the rest f[i][j] = 0.
For f[i][j], where 1 leq i leq n and 1 leq j leq x, we consider the i-th performer:
j choices, i.e., f[i - 1][j] times j;x - (j - 1) choices, i.e., f[i - 1][j - 1] times (x - (j - 1)).So the state transition equation is:
$
f[i][j] = f[i - 1][j] times j + f[i - 1][j - 1] times (x - (j - 1))
For each j, there are y^j choices, so the final answer is:
sum_{j = 1}^{x} f[n][j] times y^j
Note that since the answer can be very large, we need to take the modulo 10^9 + 7.
The time complexity is O(n times x), and the space complexity is O(n times x). Here, n and x$ represent the number of performers and the number of programs, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Combinatorial Approach | Time Complexity: |
| Dynamic Programming Approach | Time Complexity: |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Combinatorial Counting with Stirling Numbers | O(n · min(n,x)) | O(n · min(n,x)) | Best general solution when using combinatorics and modular arithmetic |
| Dynamic Programming for Stirling Numbers | O(n · min(n,x)) | O(n · min(n,x)) | Useful when deriving Stirling values directly with DP |
Leetcode Biweekly Contest 141 | 3317. Find the Number of Possible Ways for an Event | Codefod • CodeFod • 649 views views
Watch 3 more video solutions →Practice Find the Number of Possible Ways for an Event with our built-in code editor and test cases.
Practice on FleetCode