#P7223. [2023省队模拟]树

    ID: 7057 传统题 2000ms 512MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2500省选/NOI-双射计数Burnside 引理转移矩阵矩阵快速幂低秩矩阵幂降维扩大模数后精确整除欧拉函数试除法分解质因数埃氏筛快速乘防溢出

[2023省队模拟]树

题目描述

有一个包含 n+1n+1 个顶点、2n2n 条边的无向图。其中 nn 个顶点在同一个环上,另有一个顶点在环的中心。环上每对相邻顶点之间有边,每个环上顶点与中心顶点之间也有边。

求该图的生成树数量。两棵生成树视为相同,当且仅当顺时针旋转环若干步后,其中一棵与另一棵相同。旋转保持中心顶点不变。

答案对 mm 取模,mm 不一定为质数。例如 n=3n=3 时,共有 66 种生成树。

输入格式

第一行一个整数 TT,表示数据组数。

接下来 TT 行,每行两个整数 n,mn,m,分别表示环上的顶点数和模数。

输出格式

每组数据输出一行,表示答案。

样例输入

3
3 233
4 233
4 10

样例输出

6
13
3

数据范围与约定

对于所有数据,1≤T≤23331\le T\le 2333,3≤n≤1093\le n\le 10^9,2≤m≤1092\le m\le 10^9。

对于 10%10\% 的数据,n≤8n\le 8。对于 30%30\% 的数据,n≤103n\le 10^3。对于另外 30%30\% 的数据,n,mn,m 互质,且 n≤106n\le 10^6。