#P18178. Random Variables

Random Variables

Random Variables

有 nn 个相互独立的随机变量,每个变量都在整数集合 {1,2,…,m}\{1,2,\ldots,m\} 中等概率取值。

令 occ⁡i\operatorname{occ}_i 表示数值 ii 在这 nn 个变量中出现的次数,并令

M=max⁡1≤i≤mocc⁡i.M=\max_{1\le i\le m}\operatorname{occ}_i.

例如,当 n=m=5n=m=5,变量取值依次为 (4,4,3,1,5)(4,4,3,1,5) 时,出现次数为 (1,0,1,2,1)(1,0,1,2,1),所以 M=2M=2。这一组具体取值的概率为 1/31251/3125。

给定 n,mn,m,请计算 MM 的期望值 E(M)E(M)。为了使答案为整数,只需输出

E(M)⋅mn(modp).E(M)\cdot m^n\pmod p.

等价地,枚举所有 mnm^n 组有序取值,对每组的最大出现次数求和,再对 pp 取模。

输入格式

第一行两个整数 T,pT,p,满足 1≤T≤1041\le T\le10^4、2≤p≤109+72\le p\le10^9+7,分别表示测试用例数和模数。模数 pp 不保证是素数。

接下来 TT 行,每行两个整数 n,mn,m,满足 1≤n≤10001\le n\le1000、1≤m≤1091\le m\le10^9。

保证同一输入文件中所有测试用例的 nn 之和不超过 10410^4。

输出格式

每个测试用例输出一行一个整数,表示 E(M)⋅mnE(M)\cdot m^n 对给定 pp 取模的结果。

样例

输入:

3 123456789
3 2
5 5
7 7

输出:

18
7145
2066323

样例解释

第一组共有 23=82^3=8 组等概率取值。其中 (1,1,1)(1,1,1)、(2,2,2)(2,2,2) 的最大出现次数为 3,其余六组的最大出现次数为 2。因此所求整数为 2×3+6×2=182\times3+6\times2=18。