TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3811
  • 题目
  • P3811lucknum
    限制 : 时间限制 : - MS   空间限制 : 165536 KB
    评测说明 : 1000ms
    问题描述

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

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

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

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

    输入格式

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

    输出格式

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

    样例输入

    4 10 10000079 

    样例输出

    715

    提示

    前 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