Find the Number of Possible Ways for an Event
HardUpdated: Aug 2, 2025
Practice on:
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.
Examples
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
Solution
Method 1 – Stars and Bars with Power for Band Scores
Intuition
Each performer can be assigned to any of the x stages, so there are x^n ways to assign performers. After assignment, each non-empty stage (band) gets a score from 1 to y. The number of non-empty bands can range from 1 to min(n, x). For each possible number of non-empty bands k, we count:
- Ways to partition
nperformers intoknon-empty bands:S(n, k)(Stirling numbers of the second kind). - Ways to assign these bands to
xstages:P(x, k) = x! / (x-k)!. - Ways to assign scores to bands:
y^k. Sum over all possiblek.
Approach
- Precompute factorials and inverse factorials up to
max(n, x)for combinations and permutations. - Precompute Stirling numbers of the second kind
S(n, k)for allk. - For each
kfrom 1 to min(n, x):- Compute
ways = S(n, k) * P(x, k) * y^k. - Add to the answer modulo
10^9 + 7.
- Compute
- Return the total sum.
Code
C++
class Solution {
public:
int numberOfWays(int n, int x, int y) {
const int MOD = 1e9 + 7;
vector<long long> fact(max(n, x) + 2, 1), invf(max(n, x) + 2, 1);
for (int i = 1; i < fact.size(); ++i) fact[i] = fact[i-1] * i % MOD;
invf.back() = powmod(fact.back(), MOD-2, MOD);
for (int i = fact.size()-2; i >= 0; --i) invf[i] = invf[i+1] * (i+1) % MOD;
auto perm = [&](int a, int b) -> long long {
if (b > a) return 0;
return fact[a] * invf[a-b] % MOD;
};
vector<vector<long long>> S(n+1, vector<long long>(x+1));
S[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= x; ++j) {
S[i][j] = (S[i-1][j-1] + S[i-1][j] * j) % MOD;
}
}
long long ans = 0;
for (int k = 1; k <= min(n, x); ++k) {
long long ways = S[n][k] * perm(x, k) % MOD;
long long score = powmod(y, k, MOD);
ans = (ans + ways * score % MOD) % MOD;
}
return ans;
}
long long powmod(long long a, long long b, long long mod) {
long long res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
};
Go
func numberOfWays(n, x, y int) int {
mod := int(1e9 + 7)
maxv := n
if x > n {
maxv = x
}
fact := make([]int, maxv+2)
invf := make([]int, maxv+2)
fact[0] = 1
for i := 1; i < len(fact); i++ {
fact[i] = fact[i-1] * i % mod
}
invf[maxv+1] = powmod(fact[maxv+1], mod-2, mod)
for i := maxv; i >= 0; i-- {
invf[i] = invf[i+1] * (i+1) % mod
}
perm := func(a, b int) int {
if b > a {
return 0
}
return fact[a] * invf[a-b] % mod
}
S := make([][]int, n+1)
for i := range S {
S[i] = make([]int, x+1)
}
S[0][0] = 1
for i := 1; i <= n; i++ {
for j := 1; j <= x; j++ {
S[i][j] = (S[i-1][j-1] + S[i-1][j]*j) % mod
}
}
ans := 0
for k := 1; k <= n && k <= x; k++ {
ways := S[n][k] * perm(x, k) % mod
score := powmod(y, k, mod)
ans = (ans + ways*score%mod) % mod
}
return ans
}
func powmod(a, b, mod int) int {
res := 1
for b > 0 {
if b&1 == 1 {
res = res * a % mod
}
a = a * a % mod
b >>= 1
}
return res
}
Java
class Solution {
public int numberOfWays(int n, int x, int y) {
int MOD = 1000000007;
int maxv = Math.max(n, x);
long[] fact = new long[maxv+2];
long[] invf = new long[maxv+2];
fact[0] = 1;
for (int i = 1; i < fact.length; i++) fact[i] = fact[i-1] * i % MOD;
invf[maxv+1] = powmod(fact[maxv+1], MOD-2, MOD);
for (int i = maxv; i >= 0; i--) invf[i] = invf[i+1] * (i+1) % MOD;
java.util.function.BiFunction<Integer, Integer, Long> perm = (a, b) -> b > a ? 0L : fact[a] * invf[a-b] % MOD;
long[][] S = new long[n+1][x+1];
S[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= x; j++) {
S[i][j] = (S[i-1][j-1] + S[i-1][j] * j) % MOD;
}
}
long ans = 0;
for (int k = 1; k <= Math.min(n, x); k++) {
long ways = S[n][k] * perm.apply(x, k) % MOD;
long score = powmod(y, k, MOD);
ans = (ans + ways * score % MOD) % MOD;
}
return (int)ans;
}
long powmod(long a, long b, long mod) {
long res = 1;
while (b > 0) {
if ((b & 1) == 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
}
Kotlin
class Solution {
fun numberOfWays(n: Int, x: Int, y: Int): Int {
val MOD = 1_000_000_007
val maxv = maxOf(n, x)
val fact = LongArray(maxv+2) { 1L }
val invf = LongArray(maxv+2) { 1L }
for (i in 1 until fact.size) fact[i] = fact[i-1] * i % MOD
invf[maxv+1] = powmod(fact[maxv+1], MOD-2, MOD)
for (i in maxv downTo 0) invf[i] = invf[i+1] * (i+1) % MOD
fun perm(a: Int, b: Int) = if (b > a) 0L else fact[a] * invf[a-b] % MOD
val S = Array(n+1) { LongArray(x+1) }
S[0][0] = 1L
for (i in 1..n) for (j in 1..x) S[i][j] = (S[i-1][j-1] + S[i-1][j] * j) % MOD
var ans = 0L
for (k in 1..minOf(n, x)) {
val ways = S[n][k] * perm(x, k) % MOD
val score = powmod(y.toLong(), k.toLong(), MOD)
ans = (ans + ways * score % MOD) % MOD
}
return ans.toInt()
}
fun powmod(a: Long, b: Long, mod: Long): Long {
var res = 1L; var aa = a; var bb = b
while (bb > 0) {
if (bb and 1L == 1L) res = res * aa % mod
aa = aa * aa % mod
bb = bb shr 1
}
return res
}
}
Python
class Solution:
def numberOfWays(self, n: int, x: int, y: int) -> int:
MOD = 10**9 + 7
maxv = max(n, x)
fact = [1] * (maxv + 2)
invf = [1] * (maxv + 2)
for i in range(1, len(fact)):
fact[i] = fact[i-1] * i % MOD
invf[-1] = pow(fact[-1], MOD-2, MOD)
for i in range(len(fact)-2, -1, -1):
invf[i] = invf[i+1] * (i+1) % MOD
def perm(a, b):
if b > a: return 0
return fact[a] * invf[a-b] % MOD
S = [[0] * (x+1) for _ in range(n+1)]
S[0][0] = 1
for i in range(1, n+1):
for j in range(1, x+1):
S[i][j] = (S[i-1][j-1] + S[i-1][j] * j) % MOD
ans = 0
for k in range(1, min(n, x)+1):
ways = S[n][k] * perm(x, k) % MOD
score = pow(y, k, MOD)
ans = (ans + ways * score % MOD) % MOD
return ans
Rust
impl Solution {
pub fn number_of_ways(n: i32, x: i32, y: i32) -> i32 {
let n = n as usize;
let x = x as usize;
let y = y as i64;
let maxv = n.max(x);
let mut fact = vec![1i64; maxv+2];
let mut invf = vec![1i64; maxv+2];
let MOD = 1_000_000_007i64;
for i in 1..fact.len() {
fact[i] = fact[i-1] * i as i64 % MOD;
}
invf[maxv+1] = powmod(fact[maxv+1], MOD-2, MOD);
for i in (0..=maxv).rev() {
invf[i] = invf[i+1] * (i as i64 + 1) % MOD;
}
let perm = |a: usize, b: usize| -> i64 {
if b > a { 0 } else { fact[a] * invf[a-b] % MOD }
};
let mut S = vec![vec![0i64; x+1]; n+1];
S[0][0] = 1;
for i in 1..=n {
for j in 1..=x {
S[i][j] = (S[i-1][j-1] + S[i-1][j] * j as i64) % MOD;
}
}
let mut ans = 0i64;
for k in 1..=n.min(x) {
let ways = S[n][k] * perm(x, k) % MOD;
let score = powmod(y, k as i64, MOD);
ans = (ans + ways * score % MOD) % MOD;
}
ans as i32
}
}
fn powmod(mut a: i64, mut b: i64, m: i64) -> i64 {
let mut res = 1;
while b > 0 {
if b & 1 == 1 {
res = res * a % m;
}
a = a * a % m;
b >>= 1;
}
res
}
TypeScript
class Solution {
numberOfWays(n: number, x: number, y: number): number {
const MOD = 1e9 + 7;
const maxv = Math.max(n, x);
const fact = Array(maxv+2).fill(1);
const invf = Array(maxv+2).fill(1);
for (let i = 1; i < fact.length; ++i) fact[i] = fact[i-1] * i % MOD;
invf[maxv+1] = powmod(fact[maxv+1], MOD-2, MOD);
for (let i = maxv; i >= 0; --i) invf[i] = invf[i+1] * (i+1) % MOD;
const perm = (a: number, b: number) => b > a ? 0 : fact[a] * invf[a-b] % MOD;
const S = Array.from({length: n+1}, () => Array(x+1).fill(0));
S[0][0] = 1;
for (let i = 1; i <= n; ++i) {
for (let j = 1; j <= x; ++j) {
S[i][j] = (S[i-1][j-1] + S[i-1][j] * j) % MOD;
}
}
let ans = 0;
for (let k = 1; k <= Math.min(n, x); ++k) {
const ways = S[n][k] * perm(x, k) % MOD;
const score = powmod(y, k, MOD);
ans = (ans + ways * score % MOD) % MOD;
}
return ans;
}
}
function powmod(a: number, b: number, mod: number): number {
let res = 1;
while (b > 0) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
Complexity
- ⏰ Time complexity:
O(n * x + max(n, x)), for computing Stirling numbers and factorials. - 🧺 Space complexity:
O(n * x), for the DP table of Stirling numbers.