#P3500. PA2008 Cliquers

    ID: 2712 传统题 1000ms 512MiB 尝试: 197 已通过: 80 难度: 7 上传者: 标签>CF2300提高+/省选-双射计数普通生成函数递推计数费马小定理快速幂

PA2008 Cliquers

[PA2008] Cliquers

题目描述

统计结点个数为 nn,且每一个连通分量都是完全图的本质不同的图的个数 xx。

求 mx mod Pm^x \bmod P,其中 P=109−401P=10^9-401 为一个质数。

输入格式

一行两个整数,分别为 n,mn,m。

输出格式

一行一个整数,表示所求的结果。

样例 #1

样例输入 #1

3 2

样例输出 #1

8

提示

【样例解释】

当 n=3n=3 时,33 种情况如下图所示。注意您应当输出的是 mx mod P=23 mod (109−401)m^x \bmod P=2^3 \bmod (10^9-401) 的值。

【数据范围】

对于所有数据,1≤n,m≤2×1051\leq n,m\leq 2\times 10^5。