次方和

题目描述:

给定\(N\)和\(K\)，请计算

\[\sum_{i=1}^N i^K \text{ mod } 998244353\]

输入格式:

第一行一个整数 \(T\) (\(1 \le T \le 1000\))，表示数据组数。

对于每一组数据，输入一行两个整数 \(N\) (\(1 \le N \le 10^9\)) 和 \(K\)  (\(1 \le K \le 1000\))。

输出格式:

对于每一组数据，输出一行一个整数表示答案。

样例输入:

1
4 4

样例输出:

354

提示:

对于样例，有 \(1^4 + 2^4 + 3^4 + 4^4 = 1 + 16 + 81 + 256 = 354\)

时间限制: 1000ms
空间限制: 256MB

---

来源: by Massimo