Problem

You are given two integers n and k.

Initially, you start with an array a of n integers where a[i] = 1 for all 0 <= i <= n - 1. After each second, you simultaneously update each element to be the sum of all its preceding elements plus the element itself. For example, after one second, a[0] remains the same, a[1] becomes a[0] + a[1], a[2] becomes a[0] + a[1] + a[2], and so on.

Return the value of a[n - 1] after k seconds.

Since the answer may be very large, return it modulo 10^9 + 7.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


Input: n = 4, k = 5

Output: 56

Explanation:

Second | State After  
---|---  
0 | [1,1,1,1]  
1 | [1,2,3,4]  
2 | [1,3,6,10]  
3 | [1,4,10,20]  
4 | [1,5,15,35]  
5 | [1,6,21,56]

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


Input: n = 5, k = 3

Output: 35

Explanation:

Second | State After  
---|---  
0 | [1,1,1,1,1]  
1 | [1,2,3,4,5]  
2 | [1,3,6,10,15]  
3 | [1,4,10,20,35]

Constraints

  • 1 <= n, k <= 1000

Solution

Method 1 – Combinatorics (Stars and Bars)

Intuition

After each second, the update rule is equivalent to prefix sums. The value at the end, a[n-1], after k seconds, is the number of ways to distribute k indistinguishable increments among n positions, which is a classic stars and bars problem. The answer is C(n+k-1, n-1).

Approach

  1. The answer is the binomial coefficient C(n+k-1, n-1).
  2. Compute this value modulo 10^9+7 using modular inverses for efficiency.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int nthValueAfterKSeconds(int n, int k) {
        const int MOD = 1e9+7;
        vector<long long> fact(n+k,1), inv(n+k,1);
        for(int i=1;i<n+k;++i) fact[i]=fact[i-1]*i%MOD;
        inv[n+k-1]=1;
        for(int i=n+k-2;i>=0;--i) inv[i]=inv[i+1]*(i+1)%MOD;
        return fact[n+k-1]*inv[n-1]%MOD*inv[k]%MOD;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func nthValueAfterKSeconds(n, k int) int {
    const MOD = 1_000_000_007
    fact := make([]int64, n+k)
    inv := make([]int64, n+k)
    fact[0] = 1
    for i := 1; i < n+k; i++ {
        fact[i] = fact[i-1]*int64(i)%MOD
    }
    inv[n+k-1] = 1
    for i := n+k-2; i >= 0; i-- {
        inv[i] = inv[i+1]*int64(i+1)%MOD
    }
    return int(fact[n+k-1]*inv[n-1]%MOD*inv[k]%MOD)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int nthValueAfterKSeconds(int n, int k) {
        int MOD = 1_000_000_007;
        long[] fact = new long[n+k];
        long[] inv = new long[n+k];
        fact[0]=1;
        for(int i=1;i<n+k;++i) fact[i]=fact[i-1]*i%MOD;
        inv[n+k-1]=1;
        for(int i=n+k-2;i>=0;--i) inv[i]=inv[i+1]*(i+1)%MOD;
        return (int)(fact[n+k-1]*inv[n-1]%MOD*inv[k]%MOD);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun nthValueAfterKSeconds(n: Int, k: Int): Int {
        val MOD = 1_000_000_007
        val fact = LongArray(n+k){1}
        val inv = LongArray(n+k){1}
        for(i in 1 until n+k) fact[i]=fact[i-1]*i%MOD
        inv[n+k-1]=1
        for(i in n+k-2 downTo 0) inv[i]=inv[i+1]*(i+1)%MOD
        return (fact[n+k-1]*inv[n-1]%MOD*inv[k]%MOD).toInt()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def nthValueAfterKSeconds(self, n: int, k: int) -> int:
        MOD = 10**9+7
        fact = [1]*(n+k)
        for i in range(1, n+k):
            fact[i] = fact[i-1]*i%MOD
        inv = [1]*(n+k)
        inv[-1] = pow(fact[-1], MOD-2, MOD)
        for i in range(n+k-2, -1, -1):
            inv[i] = inv[i+1]*(i+1)%MOD
        return fact[n+k-1]*inv[n-1]%MOD*inv[k]%MOD
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn nth_value_after_k_seconds(n: i32, k: i32) -> i32 {
        const MOD: i64 = 1_000_000_007;
        let n = n as usize; let k = k as usize;
        let mut fact = vec![1i64; n+k];
        for i in 1..n+k { fact[i] = fact[i-1]*i as i64%MOD; }
        let mut inv = vec![1i64; n+k];
        inv[n+k-1] = pow(fact[n+k-1], MOD-2, MOD);
        for i in (0..n+k-1).rev() { inv[i] = inv[i+1]*(i as i64+1)%MOD; }
        (fact[n+k-1]*inv[n-1]%MOD*inv[k]%MOD) as i32
    }
}
fn pow(mut a: i64, mut b: i64, m: i64) -> i64 {
    let mut r = 1;
    while b > 0 {
        if b&1 == 1 { r = r*a%m; }
        a = a*a%m; b >>= 1;
    }
    r
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    nthValueAfterKSeconds(n: number, k: number): number {
        const MOD = 1_000_000_007;
        const fact = Array(n+k).fill(1);
        for(let i=1;i<n+k;++i) fact[i]=fact[i-1]*i%MOD;
        const inv = Array(n+k).fill(1);
        inv[n+k-1] = pow(fact[n+k-1], MOD-2, MOD);
        for(let i=n+k-2;i>=0;--i) inv[i]=inv[i+1]*(i+1)%MOD;
        return fact[n+k-1]*inv[n-1]%MOD*inv[k]%MOD;
    }
}
function pow(a: number, b: number, m: number): number {
    let r = 1;
    while(b>0) {
        if(b&1) r = r*a%m;
        a = a*a%m; b>>=1;
    }
    return r;
}

Complexity

  • ⏰ Time complexity: O(n+k), for factorial and inverse computation.
  • 🧺 Space complexity: O(n+k), for factorial and inverse arrays.