private static long choose(int n, int k) {
    if (k == 1) {
      return n;
    } 
    if (k == 0 || k == n) {
      return 1;
    }
    
    if (memo[n][k] != 0) {
      return memo[n][k];
    }
    long result = (choose(n, k - 1) + choose(n - 1, k - 1)) % MOD;
    memo[n][k] = result;
    return result;
  }