#P5509. 派遣

派遣

题目背景

Steve在洞穴里发现了一张地图,上面标识出了黑暗势力的据点,他决定派遣一些士兵前去

题目描述

然而,这些士兵不一定具有与黑暗势力作战的能力,因而最终被派遣的士兵是未知的

为了尽量了解派遣的士兵的情况,Steve需要你帮忙计算一些值

Steve一共有tt支军队,每支军队的人数都不同

每支军队可以按一定标准排成n×kn \times k的方阵,每个士兵的位置可以用坐标(x,y)(x,y)表示,其中0x<n,0y<k0\le x < n,0 \le y <k,这个士兵的编号就是xk+yx\cdot k+y

位于(0,0)(0,0)位置的士兵是队长,无论任何情况都会被派遣

对于其余的士兵,可以派遣,也可以不派遣

一支n×kn \times k的军队的能力值是这样定义的:

如果所有士兵都被派遣,那么能力值是11

如果位于(x,y)(x,y)位置的士兵(编号为ii)未被派遣,那么能力值变为原来的xix\frac{x}{i-x}

例如,对于一支2×22\times 2的军队,如果(1,1)(1,1)位置的士兵(编号为33)未被派遣,其他士兵都被派遣,那么能力值为131=12\frac{1}{3-1}=\frac{1}{2}

如果(1,1)(1,1)位置的士兵(编号为33)和(0,1)(0,1)位置的士兵(编号为11)都未被派遣,那么能力值为131×010=0\frac{1}{3-1} \times \frac{0}{1-0} = 0

如果(1,1)(1,1)位置的士兵(编号为33)和(1,0)(1,0)位置的士兵(编号为22)都未被派遣,那么能力值为131×121=12\frac{1}{3-1} \times \frac{1}{2-1} = \frac{1}{2}

现在,Steve需要你为每一支军队,计算出所有可能派遣方案的能力值之和

为了避免出现分数,输出结果是模11451411145141意义下的值

如果这个值不存在,那么输出1-1

也就是,如果你的答案为既约分数pq\frac{p}{q},你需要找到一个最小的非负整数aa,满足pqa(mod1145141)p\equiv q\cdot a(mod 1145141),并输出这个值,如果不存在这样的整数,就输出1-1

提示:11451411145141是质数

输入格式

第一行一个整数tt

接下来tt行,每行两个整数n,kn,k

输出格式

tt行,每行一个整数表示答案

5
2 2
3 3
1 4
2 4
3 4

3
7
1
381716
127244

提示

第四组数据实际值为73\frac{7}{3}

第五组数据实际值为559\frac{55}{9}

第一组数据解释:

如果所有士兵都被派遣,那么能力值为11

如果(1,1)(1,1)位置的士兵(编号为33)未被派遣,那么能力值为131=0.5\frac{1}{3-1}=0.5

如果(0,1)(0,1)位置的士兵(编号为11)未被派遣,那么能力值为010=0\frac{0}{1-0} = 0

如果(1,1)(1,1)位置的士兵(编号为33)和(0,1)(0,1)位置的士兵(编号为11)未被派遣,那么能力值为131×010=0\frac{1}{3-1} \times \frac{0}{1-0} = 0

如果(1,0)(1,0)位置的士兵(编号为22)未被派遣,那么能力值为121=1\frac{1}{2-1} = 1

如果(1,0)(1,0)位置的士兵(编号为22)和(1,1)(1,1)位置的士兵(编号为33)未被派遣,那么能力值为121×131=0.5\frac{1}{2-1} \times \frac{1}{3-1}=0.5

如果(1,0)(1,0)位置的士兵(编号为22)和(0,1)(0,1)位置的士兵(编号为11)未被派遣,那么能力值为121×010=0\frac{1}{2-1} \times \frac{0}{1-0}=0

如果只有队长被派遣,那么能力值为$\frac{1}{3-1} \times \frac{0}{1-0} \times \frac{1}{2-1}=0$

所以,答案为1+0.5+0+0+1+0.5+0+0=31+0.5+0+0+1+0.5+0+0=3

数据范围:

对于所有数据,n1,k2n\ge 1,k\ge 2

Subtask1是比赛时的测试数据:

测试点 分值 t nn\le kk\le
1 10 5
2 11 100
3 12 100000 5 100000
4 13 100000 5
5 16 5 100000
6 18 10910^9
7 20 100000

Subtask2包括两个不计分的Hack数据,均满足t=1t=1

#8满足#7的性质

#9满足#5的性质