\(\displaystyle S_k=\sum_{i=0}^k A_i\) \((k=0,1,\ldots,N)\) とすると、求める値は以下のように表すことができます：

\[ \begin{aligned} &\phantom{=} \sum_{1\le l\le r\le N} \left(\sum_{l\le i\le r} A_i \right)^K\\ &=\sum_{1\le l\le r\le N} \left(S_r-S_{l-1} \right)^K\\ &=\sum_{0\le l < r\le N} \left(S_r-S_l \right)^K\\ &=\sum_{0\le l < r\le N} \sum_{k=0}^K \binom Kk (-S_l)^kS_r^{K-k}\\ &=\sum_{k=0}^K\binom Kk \sum_{r=0}^N S_r^{K-k} \sum_{l=0}^{r-1} (-S_l)^k\\ \end{aligned} \]

最後の式は、 \(k\) を固定した際の値が \(\displaystyle \sum_{l=0}^{r-1} (-S_l)^k\) を \(r\) の昇順に求めていくことで \(O(N\log K)\) 時間で計算することができるので、全体として \(O(NK\log K)\) 時間で計算することができます。

各 \(i,k\) \((0\le i\le N,0\le k\le K)\) に対し \(S_i^k\) を事前に計算しておくことで \(O(NK)\) 時間に改善することも可能です。

以上を適切に実装することでこの問題に正答することができます。

実装例(C++、\(O(NK\log K)\) 時間)

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using mint = atcoder::modint998244353;
ostream &operator<<(ostream &os, mint a) { return os << a.val(); }
#define rep(i, n) for(int i = 0; i < n; i++)
int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<mint> a(n + 1);
	rep(i, n) {
		int x;
		cin >> x;
		a[i + 1] = a[i] + x;
	}
	mint ans = 0;
	rep(k, m + 1) {
		mint c = 1;
		rep(i, m) c *= i + 1;
		rep(i, k) c /= i + 1;
		rep(i, m - k) c /= i + 1;
		mint s = 0;
		rep(i, n + 1) {
			ans += a[i].pow(m - k) * s * c;
			s += (-a[i]).pow(k);
		}
	}
	cout << ans << endl;
}

実装例(C++、\(O(NK)\) 時間)

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using mint = atcoder::modint998244353;
#define rep(i, n) for(int i = 0; i < n; i++)
int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<mint> a(n + 1);
	rep(i, n) {
		int x;
		cin >> x;
		a[i + 1] = a[i] + x;
	}
	mint ans = 0;
	vector<vector<mint>> ar(m + 1, vector<mint>(n + 1));
	rep(i, n + 1) ar[0][i] = 1;
	for (int j = 1; j <= m; j++)
		rep(i, n + 1) ar[j][i] = a[i] * ar[j - 1][i];
	rep(k, m + 1) {
		mint c = 1;
		rep(i, m) c *= i + 1;
		rep(i, k) c /= i + 1;
		rep(i, m - k) c /= i + 1;
		mint s = 0;
		rep(i, n + 1) {
			ans += ar[m - k][i] * s * c;
			if (k & 1)
				s -= ar[k][i];
			else
				s += ar[k][i];
		}
	}
	cout << ans.val() << endl;
}