SP5294 REC - Recurrence

给定一个递推数列，其中 $F_0 = 1$。对于每个整数 $n \ge 1$，数列满足 $F_n = a \cdot F_{n-1} + b$。你的任务是计算 $F_n$ 模 $M$ 的值。

第一行输入一个整数 $T$，表示测试用例的数量。接下来的 $T$ 行中，每行包含四个通过空格分隔的整数 $a, b, n$ 和 $M$。

输出共 $T$ 行，每行对应一个测试用例的结果，即 $F_n \mod M$ 的值。 ## 数据范围 - $1 \le T \le 10^5$ - $1 \le a, b, n, M \le 10^9$ **本翻译由 AI 自动生成**