Random Variables
有 n 个相互独立的随机变量,每个变量都在整数集合 {1,2,…,m} 中等概率取值。
令 occi 表示数值 i 在这 n 个变量中出现的次数,并令
M=1≤i≤mmaxocci.
例如,当 n=m=5,变量取值依次为 (4,4,3,1,5) 时,出现次数为 (1,0,1,2,1),所以 M=2。这一组具体取值的概率为 1/3125。
给定 n,m,请计算 M 的期望值 E(M)。为了使答案为整数,只需输出
E(M)⋅mn(modp).
等价地,枚举所有 mn 组有序取值,对每组的最大出现次数求和,再对 p 取模。
输入格式
第一行两个整数 T,p,满足 1≤T≤104、2≤p≤109+7,分别表示测试用例数和模数。模数 p 不保证是素数。
接下来 T 行,每行两个整数 n,m,满足 1≤n≤1000、1≤m≤109。
保证同一输入文件中所有测试用例的 n 之和不超过 104。
输出格式
每个测试用例输出一行一个整数,表示 E(M)⋅mn 对给定 p 取模的结果。
样例
输入:
3 123456789
3 2
5 5
7 7
输出:
18
7145
2066323
样例解释
第一组共有 23=8 组等概率取值。其中 (1,1,1)、(2,2,2) 的最大出现次数为 3,其余六组的最大出现次数为 2。因此所求整数为 2×3+6×2=18。