CF507D The Maths Lecture

Amr 不喜欢数学，因为他觉得数学非常无聊，所以他通常在数学课上睡觉。但有一天，老师怀疑 Amr 在睡觉，于是给他出了一道题来确认他没有走神。 老师首先给了 Amr 两个正整数 $n$ 和 $k$。然后老师问 Amr，有多少个正整数 $x$ 满足以下条件： - $x$ 的十进制表示（不含前导零）恰好有 $n$ 位； - 存在某个正整数 $y$，使得： - $y$ 是 $k$ 的倍数； - $y$ 的十进制表示是 $x$ 的后缀。 由于答案可能非常大，老师让 Amr 输出答案对某个整数 $m$ 取模后的结果。 你能帮助 Amr 逃脱这个尴尬的处境吗？

输入包含三个整数 $n, k, m$，其中 $1 \leq n \leq 1000$，$1 \leq k \leq 100$，$1 \leq m \leq 10^{9}$。

输出所求数对 $m$ 取模之后的结果。

一个字符串 $S$ 的后缀是通过删除 $S$ 的前若干（可能为 0 个）字符而得到的非空字符串。 由 ChatGPT 5 翻译