#P3501. PA2008 Cliquers Strike Back

    ID: 2713 传统题 1000ms 512MiB 尝试: 108 已通过: 23 难度: 9 上传者: 标签>CF2600省选/NOI-双射计数Bell 数费马小定理中国剩余定理线性递推进位制转换递推计数滚动数组快速幂

PA2008 Cliquers Strike Back

Description

统计n个点,有标号不同分组个数X。

求m^X mod P,P=999999599是个质数。同时

P=2×13×5281×7283+1。

题目详细意思:

如果一个无向图满足:它的每个连通分量都是一个完全图(clique),并且图的顶点被编号为集合 ({1,\dots,n}) 中的数字,那么称这个图为一个 labeled cliquer(带标号的“团图”)。

Maurycy 已经把所有包含 (n) 个顶点的 labeled cliquer 都画在了一张纸上。现在他要给每一个这样的图评定“美观度”,评分是集合 1,…,m{1,\dots,m} 中的一个数(注意:不同的图允许得到相同的评分)。

问:他一共有多少种给所有这些图打分的方式?答案需要对 (109−401)(10^9 - 401) 取模。

(题面中的图示展示了 (n=3)(n=3) 时的所有 labeled cliquer。)

Format

Input

一行给出N,M

1< = N.m< =10^18。

Output

如题

Samples

3 2
32