背景

06年的浙江高考生表示不服,于是我又水了一题。

描述

设A,B是两个非空集合,如果存在一法则f,使得对A中的每个元素按法则f在B中有唯一确定的元素与之对应,则称f为从A到B的映射,记作f:A→B,映射在数学及相关的领域经常等同于函数。

设s是由1到n的所有正整数组成集合,定义映射f:A→B。

已知n,求满足f(f(x))=f(x)的映射f有多少个?

这个数可能很大,你只需要给出答案对质数p取模的值即可。

输入格式

两个空格隔开的正整数n和p。

输出格式

一个整数,表示答案对p取模的值。

样例输入

3 233

样例输出

10

数据范围与约定

  • 对于10%的数据:n\le10
  • 对于30%的数据:n\le1000
  • 对于60%的数据:n\le100000
  • 对于100%的数据:n\le2000000,10^8<p<2^{31}
  • 由于常数问题所以时限放宽至3s。

样例解释

{f(1),f(2),f(3)}的可能分别是{1,1,1},{1,1,3},{1,2,1},{1,2,2},{1,2,3},{1,3,3},{2,2,2},{2,2,3},{3,2,3},{3,3,3}。

来源

原创