派遣
题目背景
Steve在洞穴里发现了一张地图,上面标识出了黑暗势力的据点,他决定派遣一些士兵前去
题目描述
然而,这些士兵不一定具有与黑暗势力作战的能力,因而最终被派遣的士兵是未知的
为了尽量了解派遣的士兵的情况,Steve需要你帮忙计算一些值
Steve一共有$t$支军队,每支军队的人数都不同
每支军队可以按一定标准排成$n \times k$的方阵,每个士兵的位置可以用坐标$(x,y)$表示,其中$0\le x < n,0 \le y <k$,这个士兵的编号就是$x\cdot k+y$
位于$(0,0)$位置的士兵是队长,无论任何情况都会被派遣
对于其余的士兵,可以派遣,也可以不派遣
一支$n \times k$的军队的能力值是这样定义的:
如果所有士兵都被派遣,那么能力值是$1$
如果位于$(x,y)$位置的士兵(编号为$i$)未被派遣,那么能力值变为原来的$\frac{x}{i-x}$
例如,对于一支$2\times 2$的军队,如果$(1,1)$位置的士兵(编号为$3$)未被派遣,其他士兵都被派遣,那么能力值为$\frac{1}{3-1}=\frac{1}{2}$
如果$(1,1)$位置的士兵(编号为$3$)和$(0,1)$位置的士兵(编号为$1$)都未被派遣,那么能力值为$\frac{1}{3-1} \times \frac{0}{1-0} = 0$
如果$(1,1)$位置的士兵(编号为$3$)和$(1,0)$位置的士兵(编号为$2$)都未被派遣,那么能力值为$\frac{1}{3-1} \times \frac{1}{2-1} = \frac{1}{2}$
现在,Steve需要你为每一支军队,计算出所有可能派遣方案的能力值之和
为了避免出现分数,输出结果是模$1145141$意义下的值
如果这个值不存在,那么输出$-1$
也就是,如果你的答案为既约分数$\frac{p}{q}$,你需要找到一个最小的非负整数$a$,满足$p\equiv q\cdot a(mod 1145141)$,并输出这个值,如果不存在这样的整数,就输出$-1$
提示:$1145141$是质数
输入输出格式
输入格式
第一行一个整数$t$
接下来$t$行,每行两个整数$n,k$
输出格式
$t$行,每行一个整数表示答案
输入输出样例
输入样例 #1
5
2 2
3 3
1 4
2 4
3 4
输出样例 #1
3
7
1
381716
127244
说明
第四组数据实际值为$\frac{7}{3}$
第五组数据实际值为$\frac{55}{9}$
第一组数据解释:
如果所有士兵都被派遣,那么能力值为$1$
如果$(1,1)$位置的士兵(编号为$3$)未被派遣,那么能力值为$\frac{1}{3-1}=0.5$
如果$(0,1)$位置的士兵(编号为$1$)未被派遣,那么能力值为$\frac{0}{1-0} = 0$
如果$(1,1)$位置的士兵(编号为$3$)和$(0,1)$位置的士兵(编号为$1$)未被派遣,那么能力值为$\frac{1}{3-1} \times \frac{0}{1-0} = 0$
如果$(1,0)$位置的士兵(编号为$2$)未被派遣,那么能力值为$\frac{1}{2-1} = 1$
如果$(1,0)$位置的士兵(编号为$2$)和$(1,1)$位置的士兵(编号为$3$)未被派遣,那么能力值为$\frac{1}{2-1} \times \frac{1}{3-1}=0.5$
如果$(1,0)$位置的士兵(编号为$2$)和$(0,1)$位置的士兵(编号为$1$)未被派遣,那么能力值为$\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=3$
数据范围:
对于所有数据,$n\ge 1,k\ge 2$
Subtask1是比赛时的测试数据:
测试点| 分值| t | $n\le$| $k\le$
:-: | :-: | :-: | :-: | :-:
1| 10| 5| 5| 5|
2| 11| 100| 100| 100|
3| 12| 100000| 5| 100000|
4| 13| 100000| 100000| 5|
5| 16| 5| 100000| 100000|
6| 18| 5| $10^9$| $10^9$|
7| 20| 100000| $10^9$|$10^9$|
Subtask2包括两个不计分的Hack数据,均满足$t=1$
#8满足#7的性质
#9满足#5的性质