#P3113. Toy

    ID: 2235 传统题 1000ms 512MiB 尝试: 65 已通过: 23 难度: 8 上传者: 标签>CF2400提高+/省选-生成树计数Burnside 引理按不动点计数转移矩阵矩阵快速幂欧拉函数约数成对枚举试除法分解质因数同余的加减乘运算快速乘防溢出

Toy

题目描述

外面有一圈 nn 个结点,中心有一个结点与 nn 个结点都相连,总共就是 2×n2\times n 条边,删除 nn 条边,使 n+1 n+1 个点连通,旋转相同视为等价,问有多少种情况。

输出方案数 mod  m\mod m 的结果

3 10000
4 10000
4 10
6
13
3

数据规模与约定

对于 100%100\% 的数据,3≤n≤1093\le n\le 10^9,2≤m≤1092\le m \le 10^9。