# Find the N-th Value After K Seconds
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-n-th-value-after-k-seconds)
Canonical: https://scaleengineer.com/dsa/problems/find-the-n-th-value-after-k-seconds
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
---
## 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** `109 + 7`.

**Example 1:**

**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:**

**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`

# Approaches
## Direct Simulation
This approach directly simulates the process described in the problem. We maintain an array representing the state `a` at each second. We start with an array of `n` ones. Then, for `k` seconds, we repeatedly update the array by calculating the prefix sum of the current array.
**Time:** O(k * n) - We have a nested loop. The outer loop runs `k` times, and the inner loop for calculating prefix sums runs `n-1` times. · **Space:** O(n) - We use an array of size `n` to store the values at each second.
**Pros:** Simple to understand and implement as it directly models the problem statement.; Sufficiently efficient for the given constraints (`n, k <= 1000`).
**Cons:** Less efficient than the mathematical approach, with a quadratic time complexity.; Might be too slow if the constraints on `n` or `k` were larger.
### Explanation
The most straightforward way to solve this problem is to follow the simulation step-by-step. We begin with an array `a` of size `n`, where every element is `1`. The problem states that after each second, every element `a[i]` is updated to be the sum of all preceding elements plus itself. This is equivalent to calculating the prefix sum of the array.

We can perform this simulation for `k` seconds. In each second, we can update the array in-place. The new value of `a[i]` is the sum of the old values from `a[0]` to `a[i]`. This can be calculated more efficiently as `new_a[i] = new_a[i-1] + old_a[i]`. Since we iterate from left to right, `a[i-1]` will already hold its new value for the current second. Thus, the update rule simplifies to `a[i] = a[i] + a[i-1]` for `i > 0`.

We repeat this process `k` times. All additions are performed modulo `10^9 + 7` to prevent integer overflow. After `k` iterations, `a[n-1]` will hold the required value.

```java
class Solution {
    public int valueAfterKSeconds(int n, int k) {
        int MOD = 1_000_000_007;
        int[] a = new int[n];
        java.util.Arrays.fill(a, 1);

        // Simulate for k seconds
        for (int second = 0; second < k; second++) {
            // Update the array to its prefix sum
            for (int i = 1; i < n; i++) {
                a[i] = (a[i] + a[i-1]) % MOD;
            }
        }

        return a[n - 1];
    }
}
```
### Algorithm
- Define a constant `MOD` as `10^9 + 7`.
- Create an integer array `a` of size `n`.
- Initialize all elements of `a` to `1`.
- Loop `k` times, representing the seconds from `1` to `k`.
- Inside the loop, iterate from `i = 1` to `n-1`:
  - Update `a[i]` by adding the value of the preceding element: `a[i] = (a[i] + a[i-1]) % MOD`.
- After the loops complete, the value at `a[n-1]` is the final answer.

## Combinatorial Approach
A more efficient approach involves recognizing a mathematical pattern in the generated values. The values in the array after each second correspond to entries in Pascal's triangle, which can be represented by binomial coefficients. The value of `a[i]` after `t` seconds is `C(i+t, t)`. This transforms the simulation problem into a combinatorial one: calculating `C(n+k-1, k)` modulo `10^9 + 7`.
**Time:** O(n + k) - Precomputing factorials takes O(n+k) time. Modular exponentiation takes O(log(MOD)). The overall complexity is dominated by the factorial computation. · **Space:** O(n + k) - We need an array of size `n+k-1` to store the precomputed factorials.
**Pros:** Highly efficient with a linear time complexity, making it much faster than simulation.; Scales well even for larger values of `n` and `k`.
**Cons:** Requires mathematical insight to recognize the combinatorial pattern.; Implementation is more complex, involving modular inverse and modular exponentiation.
### Explanation
By observing the array's state after a few seconds, we can deduce a mathematical formula. Let `a_t[i]` be the value at index `i` after `t` seconds.
- `a_0[i] = 1 = C(i, 0)`
- `a_1[i] = i+1 = C(i+1, 1)`
- `a_2[i] = (i+1)(i+2)/2 = C(i+2, 2)`

This pattern can be proven by induction using the hockey-stick identity (`sum_{j=r to n} C(j, r) = C(n+1, r+1)`). The general formula is `a_t[i] = C(i+t, t)`. We need to find `a_k[n-1]`, which is `C((n-1)+k, k) = C(n+k-1, k)`.

To compute `C(N, K) % MOD` for a prime `MOD`, we can use the formula `C(N, K) = N! / (K! * (N-K)!)`. In modular arithmetic, this becomes `(N! * modInverse(K!) * modInverse((N-K)!)) % MOD`. Since `10^9 + 7` is prime, we can find the modular inverse using Fermat's Little Theorem: `a^(MOD-2) ≡ a^-1 (mod MOD)`. We can implement this using modular exponentiation (also known as binary exponentiation).

To make the calculation efficient, we can precompute factorials up to `N = n+k-1`.

```java
class Solution {
    private static final int MOD = 1_000_000_007;

    public int valueAfterKSeconds(int n, int k) {
        if (k == 0) return 1;
        
        // We need to calculate C(n + k - 1, k) mod MOD
        int N = n + k - 1;
        
        // Precompute factorials up to N
        long[] fact = new long[N + 1];
        fact[0] = 1;
        for (int i = 1; i <= N; i++) {
            fact[i] = (fact[i - 1] * i) % MOD;
        }

        // C(N, k) = N! / (k! * (N-k)!)
        long numerator = fact[N];
        long denominator = (fact[k] * fact[N - k]) % MOD;
        
        // Modular inverse of denominator using Fermat's Little Theorem
        long invDenominator = power(denominator, MOD - 2);
        
        return (int) ((numerator * invDenominator) % MOD);
    }

    // Modular exponentiation to calculate (base^exp) % MOD
    private long power(long base, int 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
- Identify that the value of `a[i]` after `t` seconds, `a_t[i]`, follows the pattern of a binomial coefficient: `a_t[i] = C(i+t, t)`.
- The required value is `a_k[n-1]`, which translates to `C(n-1+k, k)` or `C(n+k-1, n-1)`.
- The problem is now to compute `C(N, K) % MOD` where `N = n+k-1`, `K = k`, and `MOD = 10^9 + 7`.
- Use the formula `C(N, K) = N! / (K! * (N-K)!)`.
- To compute this modulo a prime, we use modular inverse: `C(N, K) ≡ N! * (K!)^-1 * ((N-K)!)^-1 (mod MOD)`.
- Precompute factorials up to `N` modulo `MOD` to get `N!`, `K!`, and `(N-K)!` efficiently.
- Calculate the modular inverse of `(K! * (N-K)!)` using Fermat's Little Theorem, which involves modular exponentiation: `a^(MOD-2) ≡ a^-1 (mod MOD)`.
- Multiply the numerator `N!` with the modular inverse of the denominator to get the final result.

# Solutions
### Java

```java
class Solution {
public
  int valueAfterKSeconds(int n, int k) {
    final int mod = (int)1 e9 + 7;
    int[] a = new int[n];
    Arrays.fill(a, 1);
    while (k-- > 0) {
      for (int i = 1; i < n; ++i) {
        a[i] = (a[i] + a[i - 1]) % mod;
      }
    }
    return a[n - 1];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int valueAfterKSeconds(int n, int k) {
    const int mod = 1e9 + 7;
    vector<int> a(n, 1);
    while (k-- > 0) {
      for (int i = 1; i < n; ++i) {
        a[i] = (a[i] + a[i - 1]) % mod;
      }
    }
    return a[n - 1];
  }
};

```

### Python

```python
class Solution:
    def valueAfterKSeconds(self, n: int, k: int) -> int: a = [1] * n mod = 10 ** 9 + 7 for _ in range(k): for i in range(1, n): a[i] = (a[i] + a[i - 1]) % mod return a[n - 1]

```