SP27433 DIVFIBS2 - Divisible Fibonacci Numbers

斐波那契数列的定义如下：当 $n < 2$ 时，$f_n = n$；当 $n > 1$ 时，$f_n = f_{n-1} + f_{n-2}$。这个数列类似于 $(0, 1, 1, 2, 3, 5, 8, \ldots)$。你的任务是计算数列开头的若干项中，有多少项是能被指定的整数整除的。

第一行包含一个整数 $T$，表示测试用例的数量。接下来的 $T$ 行，每行给出三个整数 $a$、$b$ 和 $k$。

对于每个测试用例，计算在区间 $[0, a^b]$ 内有多少项 $f_n$ 可以被 $k$ 整除。因为结果可能很大，输出时需要对 $10^9 + 7$ 取模。 ## 数据范围 - $T \leq 100$ - $1 \leq a, b \leq 100$ - $1 \leq k \leq 100$ **本翻译由 AI 自动生成**