Помогите найти ошибку задача Гиперфиксные суммы

Простое решение, но оно не годится на k ~ 10**9

#include <iostream>
const auto MOD = 998244353;
void solve(int* arr, const int n, int k) {
  for (auto r = 0; r < k; ++r) {
    for (auto i = 0; i < n-1; ++i) {
      arr[i+1] = (arr[i] + arr[i+1]) % MOD;
    }
  }
}
int main() {
  const int n = 20;
  int k = 1e6; int arr[]{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
  solve(arr, n, k);
  for (auto i = 0; i < n; ++i) {
    if (i) std::cout << ' ';
    std::cout << arr[i];
  }
  std::cout << std::endl;
}

Способ пошустрее — вычисляем сразу последнюю строку из первой.

/**
 * Расширенная версия алгоритма Евклида для поиска НОД
 * Помимо самого НОД находит корни уравнения x*a+y*b = gcd(a, b)
 */
int64_t gcd_ex(uint64_t a, uint64_t b, int64_t &x, int64_t &y) {
  if (a == 0) {
    x = 0; y = 1;
    return b;
  }
  int64_t x1, y1, t;
  int64_t d = gcd_ex((b+a) % a, a, x1, y1);
  t = (b / a) * x1;
  x = y1 - t;
  y = x1;
  return d;
}
/**
 * Поиск обратного a элемента b по модулю m,
 * такого, что a * b = 1 (mod m)
 */
uint64_t reciprocal_mod(uint64_t a, uint64_t m) { // a**-1 (mod m)
  int64_t x{}, y{};
  if (gcd_ex(a, m, x, y) == 1) {
    return x < 0 ? x + m : x;
  }
  std::cerr << a << " and " << m << " are not coprimes\n";
  return 1; // no reciprocal
}
void solve_sqr(int* arr, const int n, int k) {
    // A_k_i = A_0_i + \sum_{j=1}^i -1^{j-1}* \frac{k!}{j!(k-j)!}*A_0_{(i-j)}
    
    for (int i = 1; i < n; ++i) {
      // Реализация суммирования ряда по формуле выше
      uint64_t term = k;
      auto sign = 1;
      for (int j = 1; j <= i; ++j) {
        // arr[i] += sign * term * arr[i-j];
        // term = term * (k-j) / (j+1);
        uint64_t t = term;
        t = (t * sign) % MOD;
        t = (t * arr[i-j]) % MOD;
        arr[i] = (arr[i] + t) % MOD;
        term = (term * (k-j)) % MOD;
        // Деление в кольце по модулю MOD требует вычисления обратного элемента
        term = (term * reciprocal_mod(j+1, MOD)) % MOD;
        // (MOD - 1) — это просто -1 по модулю MOD
        sign = (sign == 1) ? MOD - 1 : 1;
      }
    }
}