SP25182 KBASEEN - Acceptable numbers

Byteasar 因为长时间坐在电脑前导致视力下降，不得不戴上他不喜欢的眼镜。尤其是与眼镜相关的任何事物，比如那些含有两个连续零的数字，他都会避而远之。 他正忙于研究各种不同的进制，过程中他想知道，在一个 $k$ 进制下的 $n$ 位数中，有多少个数不包含连续的两个零，也就是说有多少个数字是他能够接受的。由于可能的结果非常多，所以请输出结果对 $m$ 取模后的值。

第一行是测试用例的数量 $t$（$0 < t < 1001$）。 接下来每个测试用例包含三个整数：$n$（$0 < n < 10^{18}$）、$k$（$1 < k < 10^{18}$）和 $m$（$1 < m < 10^{18}$）。这里，$n$ 表示数字的长度，而 $k$ 表示该进制下的数码总量。

对于每个测试用例，输出满足条件的数字数量，并对 $m$ 取模后的结果。 **本翻译由 AI 自动生成**