転倒数ごとに順列の個数を数え上げる方法（挿入位置を考えていく）を思い出すと、問題は次のように言い換えられます：

\(\sum_{(x_1, \ldots, x_n)}(x_1 + \cdots + x_n)^m\) を求めよ。ただし、\(x_i\) は \(0\leq x_i < i\) を動く。

簡単のため、\(x_i\) は \(0, \ldots, i-1\) をとる確率変数として、和ではなく期待値を考えます。

この期待値は、展開したあと独立な確率変数ごとの寄与をかける形で計算できます。例えば次の要領です。

• \(E[(x_1+\cdots + x_n)^2] = \sum_i E[x_i^2] + 2\sum_{i < j}E[x_i]E[x_j]\)

するとまず、答は \(O(nm^2)\) 時間で求められます。 \(x_1, \ldots, x_n\) の指数を順に決めながら、多項係数の寄与と \(E[x_i^{m_i}]\) の値をかけていけばよいです。

\(m\) を固定すると、期待値は \(n\) の多項式になることが分かります。このことを確かめましょう。 \(\sum_{i < j}\) のような条件が邪魔ですが、これは \(\sum_{1\leq i, j\leq n} - \sum_{i=j}\) のような変形を考えることで、\(\sum_{1\leq i,j\leq n}\) のような和に帰着できます（多項式を分割束で包除しても多項式）。つまり、固定した \((a, b, c, \ldots)\) に対して \(\sum_{i=1}^nE[x_i^a]\sum_{i=1}^nE[x_i^b]\sum_{i=1}^nE[x_i^c]\cdots\) というような式が \(n\) の多項式になることを示せばよいです。多項式の積は多項式なので、結局定数 \(a\) に対して \(\sum_{i=1}^n E[x_i^a]\) が \(n\) の多項式になることを確認すればよく、これは容易です。

したがって、小さい \(n\) で答を求めておいたあと、多項式補間をすることで大きい \(n\) の解を計算できます。

前計算 \(O(m^3)\)、クエリ \(O(m)\) の計算量が達成できます。

（追記）前計算の dp をよく見ると畳み込みの形になっているので、前計算 \(O(m^2\log m)\)、クエリ \(O(m)\) にできます。