小强的积木

时间限制:10s      空间限制:128MB

题目描述

 


输入格式

两个正整数N(N<=1,000,000,000),P(P<=100,000,000)。保证P是一个质数。


输出格式

你要输出N个小单元组成的积木的数量模P的值。


样例输入

3 997

样例输出

12

提示

【样例解释】
    以下展示了这12种可能的积木。把每个数字想象成一个单位,相同的数字属于同一块积木。
111   112    122   123  


11


12

 2
11

 3
12

22

23

22

3
2
1
【数据说明】
       对于100%的数据,N<=1000000000。P<=100000000


题目来源

没有写明来源