Find the Number of Possible Ways for an Event

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

Understanding the Visualization

Input

n=3 performers, x=2 stages, y=2 possible scores

Assignment

Each performer chooses one of x stages

Scoring

Each active stage (band) gets a score from 1 to y

Key Takeaway

🎯 Key Insight: Multiply assignment possibilities by scoring possibilities, using inclusion-exclusion to count exactly k active stages

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

Approach	Time	Space	Notes
✓ Direct Mathematical Formula	O(x²)	O(1)	Calculate result directly using the formula: sum over k of Stirling numbers × combinations × powers
Brute Force with Inclusion-Exclusion	O(x²)	O(1)	Use inclusion-exclusion principle to count valid assignments and multiply by scoring possibilities

Direct Mathematical Formula — Algorithm Steps

Step 1: For each k from 1 to min(n,x), compute Stirling number S(n,k)
Step 2: Multiply by C(x,k) to choose which k stages to use
Step 3: Multiply by y^k for scoring possibilities and sum results

Visualization

Tap to expand

Step-by-Step Walkthrough

Partition

Use S(n,k) to count ways to partition n performers into k groups

Assign

Assign each group to one of C(x,k) stage combinations

Score

Each of k stages gets scored in y^k ways

Code -

solution.c — C

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

const int MOD = 1000000007;

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;
}

long long factorial(int k) {
    long long result = 1;
    for (int i = 1; i <= k; i++) {
        result = (result * i) % MOD;
    }
    return result;
}

long long stirling2(int n, int k) {
    if (k > n || k <= 0) return 0;
    if (k == 1 || k == n) return 1;
    
    long long result = 0;
    for (int i = 0; i <= k; i++) {
        long long sign = i % 2 == 0 ? 1 : -1;
        long long term = (sign * comb(k, i) * powMod(k - i, n)) % MOD;
        result = (result + term + MOD) % MOD;
    }
    
    return (result * powMod(factorial(k), 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 = stirling2(n, k);
        long long stageChoices = comb(x, k);
        long long scoreWays = powMod(y, k);
        
        result = (result + (ways * stageChoices % MOD * scoreWays % MOD)) % MOD;
    }
    
    return result;
}

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²)

Computing Stirling numbers S(n,k) for each k requires O(k) inclusion-exclusion terms

✓ Linear Growth

Space Complexity

O(1)

Only variables needed for computation, no auxiliary arrays

✓ 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Direct Mathematical Formula — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler