O - Simple Inversion Problem Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

長さ N の順列全てに対する転倒数の M 乗の総和を 998244353 で割ったあまりを求めてください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1 \le T \le 1000
  • 2 \le N \le 10^7
  • 1 \le M \le 100
  • 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

T
\mathrm{Case}_1
\mathrm{Case}_2
\vdots
\mathrm{Case}_T

各テストケースは以下の形式で与えられる。

N M

出力

T 行出力せよ。i 行目には \mathrm{Case}_i の答えを出力せよ。

入力例 1

4
3 2
4 1
53 54
1234 12

出力例 1

19
72
403070452
49172397

1 個目のテストケースでは、0+1+1+4+4+9=19 より、19 が解です。