Find the Number of Possible Ways for an Event - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: n = 1, x = 2, y = 3

› Output: 6

💡 Note: 1 performer can go to stage 1 or 2 (2 ways). Each stage can get score 1, 2, or 3 (3 ways). Total: 2 × 3 = 6 ways.

Example 2 — Multiple Performers

$ Input: n = 2, x = 2, y = 2

› Output: 10

💡 Note: Assignments: (1,1), (1,2), (2,1), (2,2). Only 1 stage used: 2 ways × C(2,1) × 2¹ = 8. Both stages used: 2 ways × C(2,2) × 2² = 8. But we subtract overlaps using inclusion-exclusion to get 10.

Example 3 — Single Stage

$ Input: n = 3, x = 1, y = 4

› Output: 4

💡 Note: All 3 performers must go to the single stage (1 way). That stage can be scored 1, 2, 3, or 4 (4 ways). Total: 1 × 4 = 4 ways.

Constraints

1 ≤ n ≤ 1000
1 ≤ x ≤ 1000
1 ≤ y ≤ 10⁹

Visualization

Tap to expand

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to count stage assignments and scoring separately. We need to sum over all possible numbers of active stages k, counting assignments where exactly k stages are used (using inclusion-exclusion or Stirling numbers), then multiply by ways to choose those stages and score them. Best approach uses Stirling numbers of the second kind with Time: O(x²), Space: O(1).

Common Approaches

✓ Brute Force with Inclusion-Exclusion

⏱️ Time: O(x²) Space: O(1)

For each possible number of active stages k, use inclusion-exclusion to count assignments where exactly k stages are used, then multiply by y^k scoring possibilities.

Direct Mathematical Formula

⏱️ Time: O(x²) Space: O(1)

Use Stirling numbers of the second kind to count surjective functions (assignments where all selected stages are used), then multiply by stage selection and scoring possibilities.

Brute Force with Inclusion-Exclusion — Algorithm Steps

Step 1: For each k from 1 to min(n,x), count assignments using exactly k stages
Step 2: Use inclusion-exclusion: C(x,k) * (k^n - C(k,1)*(k-1)^n + C(k,2)*(k-2)^n - ...)
Step 3: Multiply by y^k for scoring possibilities and sum all results

Visualization

Tap to expand

Step-by-Step Walkthrough

Choose Stages

Select k stages out of x total stages

Apply Inclusion-Exclusion

Count assignments where all k stages are used

Multiply Scores

Each active stage gets one of y possible scores

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

const long long MOD = 1000000007LL;

long long powMod(long long base, int exp) {
    long long result = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1) {
            result = (result * base) % MOD;
        }
        exp >>= 1;
        base = (base * base) % MOD;
    }
    return result;
}

long long comb(int n, int k) {
    if (k > n || k < 0) return 0;
    if (k == 0 || k == n) return 1;
    
    long long num = 1, den = 1;
    for (int i = 0; i < k; i++) {
        num = (num * (n - i)) % MOD;
        den = (den * (i + 1)) % MOD;
    }
    
    return (num * powMod(den, MOD - 2)) % MOD;
}

int min(int a, int b) {
    return a < b ? a : b;
}

int solution(int n, int x, int y) {
    long long result = 0;
    
    for (int k = 1; k <= min(n, x); k++) {
        long long ways = 0;
        for (int i = 0; i <= k; i++) {
            long long sign = i % 2 == 0 ? 1 : -1;
            ways = (ways + sign * comb(k, i) * powMod(k - i, n)) % MOD;
        }
        
        long long stageChoices = comb(x, k);
        long long scoreWays = powMod(y, k);
        
        result = (result + (ways * stageChoices % MOD * scoreWays % MOD)) % MOD;
    }
    
    return (int)((result + MOD) % MOD);
}

int main() {
    int n, x, y;
    scanf("%d", &n);
    scanf("%d", &x);
    scanf("%d", &y);
    
    printf("%d\n", solution(n, x, y));
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(x²)

For each of x possible active stages, we compute inclusion-exclusion with x terms

✓ Linear Growth

Space Complexity

O(1)

Only storing variables for computation, no extra data structures

✓ Linear Space

8.2K Views

Medium Frequency

~35 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Find the Number of Possible Ways for an Event - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with Inclusion-Exclusion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler