Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
统计

有一天白银御行问了四宫辉夜一个问题,一张二分图左边有n个点,右边有m个点,一个左边的点和一个右边的点之间的期望距离是多少呢?(黑体:如果两点不连通距离为0)众所周知,辉夜大小姐是个IT白痴,这一下就难倒了辉夜大小姐,眼看白银御行就要胜利,可爱又傲娇的四宫辉夜向你求助,你能帮辉夜大小姐反败为胜吗?

输入 一个T表示数据组数,接下来T行,每行三个数表示n,m,P,表示左边有n个点,右边有m个点,P是一个质数。

输出 输出一共有T行,每行一个数表示,模P意义下的一对点(一个左边的点和一个右边的点)期望距离。

数据规模

100%的数据保证T=3,772001<= P <= 1e9 + 7且是一个质数,n,m在数据规模内等概率随机生成,P是在[772001,1e9+7]以内的等随机生成一个数,再向下找到最近的素数。

数据点编号 n m
1-3 1<=n<=8 1<=m<=8
4 8<=n<=10 8<=m<=10
5-7 10<=n<=30 1<=m<=10
8-10 20<=n<=30 20<=m<=30
样例:

输入:
3
4 5 457119869
1 2 615141817
5 1 72753481
输出:
413570425
307570909
36376741