CF1808E1 Minibuses on Venus (easy version)

这是该问题的简单版本。三个版本之间唯一的区别在于 $n$ 和 $k$ 的约束条件。只有在解决了所有版本的问题后，你才能进行 Hack。 Maxim 是金星上的一名小巴司机。 要乘坐 Maxim 的小巴，你需要一张车票。每张车票上都有一个由 $n$ 位数字组成的号码。然而，众所周知，金星居民使用的是 $k$ 进制数字系统，而不是十进制。因此，车票号码可以看作是一个由 $n$ 个整数（每个整数在 $0$ 到 $k-1$ 之间，包括 $0$ 和 $k-1$）组成的序列。 金星居民认为一张车票是幸运的，当且仅当车票上存在某一位数字等于其余所有数字之和对 $k$ 取模的结果。举例来说，如果 $k=10$，那么车票 $7135$ 是幸运的，因为 $7+1+5 \equiv 3 \pmod{10}$。而车票 $7136$ 不是幸运的，因为没有任何一位数字等于其余数字之和对 $10$ 取模的结果。 有一次在旅途中，Maxim 想知道一共有多少张幸运车票。同时，Maxim 也明白这个数字可能非常大，因此他只关心答案对某个质数 $m$ 取模的结果。

输入仅一行，包含三个整数 $n$、$k$ 和 $m$（$1 \le n \le 100$，$1 \le k \le 30$，$10^8 \le m \le 10^9 + 7$，$m$ 是质数），分别表示车票的位数、金星的进制数和用于取模的质数。

输出一个整数，表示幸运车票的数量对 $m$ 取模的结果，即答案除以 $m$ 的余数。

在第一个样例中，只有四张幸运车票：$000$、$011$、$101$ 和 $110$。 由 ChatGPT 4.1 翻译