← 返回题目列表

Codeforces · 507/D

D. 数学讲座

中文机器翻译题面 查看原题

Amr 不喜欢数学,因为他觉得数学很无聊,所以他通常在数学课上睡觉。但有一天,老师怀疑 Amr 正在睡觉,并问了他一个问题,以确定他没有睡觉。

首先,他给了 Amr 两个正整数 n 和 k。然后他问 Amr,存在多少个整数 x > 0 使得:

- x 的十进制表示形式(不带前导零)恰好由 n 位数字组成;
- 存在某个整数 y > 0 使得: $$y \bmod k = 0$$; y 的十进制表示形式是 x 的十进制表示形式的后缀。

由于这个问题的答案可能相当大,老师要求 Amr 仅输出对数 m 取模后的余数。

你能帮助Amr摆脱这种尴尬的境地吗?

输入

输入由三个整数 n、k、m 组成(1 ≤ n ≤ 1000、1 ≤ k ≤ 100、1 ≤ m ≤ 109)。

输出

打印所需的模 m 数。

示例

输入 #1

1 2 1000

输出 #1

4

输入 #2

2 2 1000

输出 #2

45

输入 #3

5 3 1103

输出 #3

590

注意

字符串 S 的后缀是一个非空字符串,可以通过从 S 中删除一些(可能是零)第一个字符来获得。