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 中删除一些(可能是零)第一个字符来获得。