有一天白银御行问了四宫辉夜一个问题,一张二分图左边有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