Find the n th value after k seconds

Array Math Simulation Combinatorics Prefix Sum

53.8% acceptance

Feb 24, 2026

122

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. Return the value of a[n - 1] after k seconds, modulo 10^9 + 7.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn value_after_k_seconds(n: i32, k: i32) -> i32 {
    const MOD: u64 = 1_000_000_007;
    // a[n-1] after k seconds = C(n+k-1, k) mod MOD
    // Compute C(n+k-1, min(n-1, k))
    let m = (n + k - 1) as usize; // total
    let r = k.min(n - 1) as usize; // smaller of the two

    let mut fact = vec![1u64; m + 1];
    for i in 1..=m {
      fact[i] = fact[i - 1] * i as u64 % MOD;
    }

    let mod_pow = |mut a: u64, mut b: u64| -> u64 {
      let mut res = 1u64;
      a %= MOD;
      while b > 0 {
        if b & 1 == 1 {
          res = res * a % MOD;
        }
        a = a * a % MOD;
        b >>= 1;
      }
      res
    };

    (fact[m] * mod_pow(fact[r], MOD - 2) % MOD * mod_pow(fact[m - r], MOD - 2) % MOD) as i32
  }
}