身高问题（concert）

题目描述

日本演唱会门票的售卖方式是先抽后卖，所以如果想要抢到一个好的位置一定不要忘记参与抽选活动哦！由于位置抽选的方式是随机的，可能会在观看演唱会时出现这种情况：前面的人比后面的人高，导致到后面的看不到小绿毛。

同一排上的观众是不会相互遮挡的，所以我们在这里只在意一列长度为 $n$ 的座位。从舞台向外将座位编号为 $1,2,\dots,n$，且这 $n$ 的人的身高是 $1,2,\dots,n$。如果位置 $i$ 的人前面有 $a$ 个比他要高的人，那么他就会产生 $a$ 点怒气。对于这 $n$ 个人，一个座位顺序的怒气值 $A$ 是所有人的怒气和，每个人坐到每个位置的概率是相等的。你坐在 SVIP 座，所以不参与排座，看着他们生气会产生 $k^A+A^2$ 的惬意（什么资本家。。。）。

现在你想知道，对于所有可能的座位顺序，你产生的惬意总和。答案对 $10^9+7$ 取模。

简要题意：

设 $P$ 为任意一个 $1 \sim n$ 的排列，$\tau(P)$ 为其中的逆序对个数，求（答案对 $10^9+7$ 取模） $$ \sum_{p \in \operatorname{permutation}(n) } \left( k^{\tau(P)} + \tau^2(P) \right) $$

输入格式

本题为多组数据，第一行为数据组数 $T$。

对于每组数据，一行两个正整数 $n$，$k$。意义为题目中所述。

输出格式

对于每组数据，一行一个整数。

样例

输入 #1

1
3 2

输出 #1

40

说明/提示

对于 $10\%$ 的数据：$T=1,n \le 10, k \le 2$

对于 $30\%$ 的数据：$T=1,n \le 100, k \le 2$

另外有 $5\%$ 的数据：$n=1,k \le 1e9$

对于 $100\%$ 的数据：$\sum n \le 10^7, T \le 10^6, 2 \le k \le 10^9$

对于 $0\%$ 的数据：$\sum n \le 10^{12}$