以下のように問題を言い換えます。

• \(N\) 個の箱が横一列に並んでいる。\(i\) 番目の箱には \(A_i\) 個のボールが入っている。
• 以下の一連の操作を行う方法は何通りあるか？
  1. 箱の列の間に仕切りを \(2\) つ入れる。ただし、仕切り同士は区別できない。
  2. \(i=1,2,\dots,K\) それぞれについて、\(2\) つの仕切りの間にある箱の中にあるボールを一つ選んで、そのボールに \(i\) と書かれたシールを貼る。一つのボールに複数枚のシールを貼ってもよい。

元のシグマの式との対応づけとしては、\(2\) つの仕切りの位置を定めることが \(1\) つめのシグマにおける \(l,r\) の値を固定することに該当し、仕切りの位置が定まった上で \(K\) 枚のシールを貼る場合の数が、固定された \(l,r\) における \((\sum_{l\leq i\leq r} A_i)^K\) の値に一致します。

箱の列を左から順に見ていって、仕切りの位置を定めつつ、同時にシールを貼っていくことを考えましょう。以下のような DP を行います。

• \(\mathrm{dp}[i][j][k]\): \(i\) 個目の箱まで見て、今までに仕切りを \(j\ (0\leq j\leq 2)\) 個挿入し、シールを \(k\ (0\leq k\leq K)\) 個貼ったときの場合の数

遷移は以下の \(3\) 通りです。

• \(\mathrm{dp}[i][j+1][k]\) += \(\mathrm{dp}[i][j][k]\)
• \(\mathrm{dp}[i+1][j][k]\) += \(\mathrm{dp}[i][j][k]\)
• \(\mathrm{dp}[i+1][1][k+p]\) += \(\mathrm{dp}[i][1][k] \times \binom{K-k}{p} \times A_i^p\ \ \ (1 \leq p\leq K-k)\)

一つ目の遷移は仕切りを挿入することに、二つ目の遷移はシールを貼らずに次の箱へ進むことに対応しています。三つ目の遷移は今見ている箱の中のボールにシールを貼ることに対応し、

• 変数 \(p\) はシールを貼る個数
• 係数 \(\binom{K-k}{p}\) は、まだ貼られていない \(K-k\) 個のシールの中から今貼る \(p\) 個のシールを選ぶ場合の数
• 係数 \(A_i^p\) は、今貼る \(p\) 個のシールそれぞれについて、そのシールを貼るボールを選ぶ場合の数

にそれぞれ対応します。なお、三つ目の遷移が \(j=1\) の場合に限定されているのは、シールは \(2\) つの仕切りの間にある箱の中のボールにしか貼れないためです。

計算量は \(O(NK^2)\) です。

実装例 (C++) :

#include <bits/stdc++.h>
#include <atcoder/modint>

using namespace std;

using mint = atcoder::modint998244353;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int &i: a) cin >> i;
    vector binom(k + 1, vector<mint>(k + 1));
    for (int i = 0; i <= k; i++) {
        binom[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            binom[i][j] = binom[i - 1][j] + binom[i - 1][j - 1];
        }
    }
    vector dp(n + 1, vector<mint>(k + 1));
    mint ans = 0;
    for (int i = 0; i < n; i++) {
        vector<mint> pw(k + 1); // pw[j] = (a[i])^j
        pw[0] = 1;
        for (int j = 0; j < k; j++) {
            pw[j + 1] = pw[j] * a[i];
        }
        dp[i][0] += 1;
        for (int j = 0; j <= k; j++) {
            for (int l = 0; j + l <= k; l++) {
                dp[i + 1][j + l] += dp[i][j] * binom[k - j][l] * pw[l];
            }
        }
        ans += dp[i + 1][k];
    }
    cout << ans.val() << endl;
}

なお、上記の実装例では少しばかりの工夫を加えることで、DP の \(2\) 番目のキー \(j\) を削減しています。どのように削減しているのかぜひ考えてみてください。（ヒント：28, 34 行目）