TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3811
  • Problem
  • P3811lucknum
    Limits : Time Limit : - MS   Memory Limit : 165536 KB
    Judgment Tips : 1000ms
    Description

    每个人都会有幸运数字,有种幸运数字是这样定义的:

    如果X是幸运数字,则X在m进制下的表示为x1x2...xk,一定有x1<=x2<=...<=xk,其中k可以表示X在m进制下的位数(不能有前导0,除非该数本身就是0)。

    这样的数字可能有无穷多个的,但是如果是在m进制下位数不超过n的幸运数字,就应该是有限个了,你能算出来吗?

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

    Input Format

    共一行,三个正整数 n、m 和 p,保证 p 是质数。 

    Output Format

    共一行,表示答案对p取模的值。

    Sample Input

    4 10 10000079 

    Sample Output

    715

    Hint

    前 20%的数据满足 n <= 18, m <= 10。

    前 50%的数据满足 n <= 100, m <= 100。

    前 80%的数据满足 n <= 1000, m <= 1000。

    100%的数据满足 n <= 10^7, m <= 10^7, n + m <= p, p <= 10000079