次方和

题目描述:

给定$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