# Find the Number of Possible Ways for an Event
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-the-number-of-possible-ways-for-an-event)
Canonical: https://scaleengineer.com/dsa/problems/find-the-number-of-possible-ways-for-an-event
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics)
---
## 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** `109 + 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 = 3

**Output:** 6

**Explanation:**

* There are 2 ways to assign a stage to the performer.
* The jury can award a score of either 1, 2, or 3 to the only band.

**Example 2:**

**Input:** n = 5, x = 2, y = 1

**Output:** 32

**Explanation:**

* Each performer will be assigned either stage 1 or stage 2.
* All bands will be awarded a score of 1.

**Example 3:**

**Input:** n = 3, x = 3, y = 4

**Output:** 684

**Constraints:**

* `1 <= n, x, y <= 1000`

# Approaches
## Dynamic Programming
We can solve this problem using dynamic programming. We build a solution for `n` performers based on the solution for `n-1` performers. Let `dp[i][j]` be the number of ways to assign `i` performers to `x` stages such that exactly `j` stages are occupied. We can derive a recurrence relation for `dp[i][j]`. The final answer is obtained by summing up the ways for all possible numbers of occupied stages, each weighted by the number of ways to assign scores.
**Time:** O(n * min(n, x)). The nested loops run for `sum_{i=1 to n} min(i, x)` iterations, which simplifies to `O(n*min(n,x))`. · **Space:** O(x) for the space-optimized DP array.
**Pros:** Relatively simple to understand and implement.; The logic follows a natural step-by-step build-up.
**Cons:** It is asymptotically slower than the combinatorial approach, especially when `n` is much larger than `x`.
### Explanation
Let `dp[i][j]` be the number of ways to assign `i` performers to `x` stages, resulting in exactly `j` occupied stages. To compute `dp[i][j]`, we consider the `i`-th performer. This performer can either be assigned to one of the `j` stages already occupied by the first `i-1` performers, or to one of the `x-(j-1)` empty stages.

This leads to the recurrence: `dp[i][j] = dp[i-1][j] * j + dp[i-1][j-1] * (x - j + 1)`.

The base case is `dp[0][0] = 1` (0 performers, 0 occupied stages, 1 way).

We can build a DP table of size `(n+1) x (min(n, x)+1)`. After computing `dp[n][j]` for all `j` from `1` to `min(n, x)`, we can find the total number of ways. For a fixed `j`, there are `dp[n][j]` ways to form `j` bands. Each of these `j` bands can be awarded a score from `1` to `y`, giving `y^j` ways to assign scores.

The total number of ways is `sum_{j=1 to min(n, x)} (dp[n][j] * y^j)`.

All calculations should be done modulo `10^9 + 7`. The space complexity can be optimized from `O(n*x)` to `O(x)` by noticing that `dp[i]` only depends on `dp[i-1]`, allowing for an in-place update.

```java
class Solution {
    long MOD = 1_000_000_007;

    public int numberOfWays(int n, int x, int y) {
        long[] dp = new long[x + 1];
        dp[0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = Math.min(i, x); j >= 1; j--) {
                long term1 = (dp[j] * j) % MOD;
                long term2 = (dp[j - 1] * (x - j + 1)) % MOD;
                dp[j] = (term1 + term2) % MOD;
            }
        }

        long totalWays = 0;
        for (int j = 1; j <= Math.min(n, x); j++) {
            long waysForJStages = dp[j];
            long scoreWays = power(y, j);
            totalWays = (totalWays + (waysForJStages * scoreWays) % MOD) % MOD;
        }

        return (int) totalWays;
    }

    private long power(long base, long exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }
}
```
### Algorithm
- Let `dp[i][j]` be the number of ways to assign `i` performers to `x` stages, resulting in exactly `j` occupied stages.
- The recurrence relation is `dp[i][j] = (dp[i-1][j] * j + dp[i-1][j-1] * (x - j + 1)) % MOD`.
- The base case is `dp[0][0] = 1`.
- We can use a 1D array `dp` of size `x+1` to optimize space. `dp[j]` will store the number of ways to assign the current number of performers to occupy `j` stages.
- The algorithm proceeds as follows:
  1. Initialize a 1D array `dp` of size `x+1`, with `dp[0] = 1`.
  2. Loop for `i` from `1` to `n` (performers).
  3. In an inner loop, update `dp[j]` for `j` from `min(i, x)` down to `1` using the recurrence.
  4. After the loops, `dp[j]` contains the number of ways to assign `n` performers to occupy `j` stages.
  5. The total number of ways is the sum of `dp[j] * y^j` for `j` from `1` to `min(n, x)`.
  6. A modular exponentiation function is needed to compute `y^j`.

## Combinatorics with Inclusion-Exclusion
This problem can be modeled using combinatorial principles. The total number of ways is the sum over the number of occupied stages, `k`. For each `k`, we need to find the number of ways to choose `k` stages, the number of ways to assign `n` performers to exactly these `k` stages (surjections), and the number of ways to assign scores to the `k` resulting bands. The number of surjections can be calculated using the principle of inclusion-exclusion.
**Time:** O(min(n, x)^2 + min(n, x) * log n). Precomputation takes `O(x + min(n, x) * log n)`. The main calculation involves nested loops summing up to `O(min(n, x)^2)` operations. · **Space:** O(x + min(n, x)) which simplifies to O(x) since `min(n, x) <= x`. This is for storing precomputed factorials and powers.
**Pros:** Asymptotically faster than the DP approach, especially when `n` is much larger than `x`.; It is a very efficient method for the given constraints.
**Cons:** The combinatorial formula is more complex and might be less intuitive to derive than the DP recurrence.
### Explanation
The total number of ways can be expressed as a sum over `k`, the number of occupied stages:
`TotalWays = sum_{k=1 to min(n, x)} (Ways to choose k stages) * (Ways to assign n performers to these k stages surjectively) * (Ways to score k bands)`.

- **Ways to choose k stages from x:** `C(x, k)`.
- **Ways to assign n performers to k specific stages such that none are empty:** This is the number of surjective functions from a set of `n` elements to a set of `k` elements, denoted `Sur(n, k)`. It can be calculated using the inclusion-exclusion formula: `Sur(n, k) = sum_{j=0 to k} (-1)^(k-j) * C(k, j) * j^n`.
- **Ways to score k bands:** `y^k`.

The final formula is: `TotalWays = sum_{k=1 to min(n, x)} C(x, k) * Sur(n, k) * y^k`.

We can compute this sum efficiently. We need to precompute factorials and their modular inverses to calculate combinations `C(a, b)` quickly. We also precompute powers `j^n` to speed up the calculation of `Sur(n, k)`.

```java
class Solution {
    long MOD = 1_000_000_007;
    long[] fact;
    long[] invFact;

    public int numberOfWays(int n, int x, int y) {
        int m = Math.min(n, x);
        precomputeFactorials(x);

        long[] pow_j_n = new long[m + 1];
        for (int j = 0; j <= m; j++) {
            pow_j_n[j] = power(j, n);
        }

        long totalWays = 0;
        long y_k = 1;

        for (int k = 1; k <= m; k++) {
            y_k = (y_k * y) % MOD;

            long sur_n_k = 0;
            for (int j = 0; j <= k; j++) {
                long term = (combinations(k, j) * pow_j_n[j]) % MOD;
                if ((k - j) % 2 == 1) {
                    sur_n_k = (sur_n_k - term + MOD) % MOD;
                } else {
                    sur_n_k = (sur_n_k + term) % MOD;
                }
            }

            long combinations_x_k = combinations(x, k);
            long term = (combinations_x_k * sur_n_k) % MOD;
            term = (term * y_k) % MOD;
            
            totalWays = (totalWays + term) % MOD;
        }

        return (int) totalWays;
    }

    private void precomputeFactorials(int maxVal) {
        fact = new long[maxVal + 1];
        invFact = new long[maxVal + 1];
        fact[0] = 1;
        invFact[0] = 1;
        for (int i = 1; i <= maxVal; i++) {
            fact[i] = (fact[i - 1] * i) % MOD;
            invFact[i] = power(fact[i], MOD - 2);
        }
    }

    private long combinations(int n, int k) {
        if (k < 0 || k > n) {
            return 0;
        }
        return (((fact[n] * invFact[k]) % MOD) * invFact[n - k]) % MOD;
    }

    private long power(long base, long exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }
}
```
### Algorithm
- The total number of ways is `sum_{k=1 to min(n, x)} C(x, k) * Sur(n, k) * y^k`.
- `C(x, k)` is the number of ways to choose `k` stages from `x`.
- `Sur(n, k)` is the number of ways to assign `n` performers to `k` stages such that every stage is occupied (a surjection). It's calculated using the inclusion-exclusion principle: `Sur(n, k) = sum_{j=0 to k} (-1)^(k-j) * C(k, j) * j^n`.
- `y^k` is the number of ways to assign scores to the `k` bands.
- The algorithm is as follows:
  1. Let `m = min(n, x)`.
  2. Precompute factorials and their modular inverses up to `x` to calculate `C(a, b)` in `O(1)`.
  3. Precompute `j^n % MOD` for `j` from `0` to `m`.
  4. Initialize `totalWays = 0`.
  5. Loop `k` from `1` to `m`.
  6. Inside the loop, calculate `Sur(n, k)` using its formula and the precomputed values.
  7. Calculate the full term `C(x, k) * Sur(n, k) * y^k` and add it to `totalWays`.
  8. Return `totalWays`.

# Solutions
### Java

```java
class Solution {
public
  int numberOfWays(int n, int x, int y) {
    final int mod = (int)1 e9 + 7;
    long[][] f = new long[n + 1][x + 1];
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= x; ++j) {
        f[i][j] =
            (f[i - 1][j] * j % mod + f[i - 1][j - 1] * (x - (j - 1) % mod)) %
            mod;
      }
    }
    long ans = 0, p = 1;
    for (int j = 1; j <= x; ++j) {
      p = p * y % mod;
      ans = (ans + f[n][j] * p) % mod;
    }
    return (int)ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numberOfWays(int n, int x, int y) {
    const int mod = 1e9 + 7;
    long long f[n + 1][x + 1];
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= x; ++j) {
        f[i][j] =
            (f[i - 1][j] * j % mod + f[i - 1][j - 1] * (x - (j - 1) % mod)) %
            mod;
      }
    }
    long long ans = 0, p = 1;
    for (int j = 1; j <= x; ++j) {
      p = p * y % mod;
      ans = (ans + f[n][j] * p) % mod;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numberOfWays(self, n: int, x: int, y: int) -> int: mod = 10 ** 9 + 7 f = [[0] * (x + 1) for _ in range(n + 1)] f[0][0] = 1 for i in range(1, n + 1): for j in range(1, x + 1): f[i][j] = (f[i - 1][j] * j + f[i - 1][j - 1] * (x - (j - 1))) % mod ans, p = 0, 1 for j in range(1, x + 1): p = p * y % mod ans = (ans + f[n][j] * p) % mod return ans

```