题目描述

你已经做了斐波那契数列的和。但是连续的太简单，没意思。于是你打算挑战不连续的，但是为了表示方便，我们考虑等间距的斐波那契数列的和。

同样定义斐波那契数列 $f(0)=0,f(1)=1,f(n)_{n≥2}=f(n-2)+f(n-1)$。

给定 $k,b,n,m$，求： $(\sum_{0≤i<n} f(k×i+b)) \% m$

输入格式

第一行是一个整数 $T(1≤T≤10^5)$，表示测试数据则组数。

接下来 $T$ 行，每行四个整数 $k,b,n,m$，意义如前所述。$0≤b≤10^9$，$1≤k,n,m≤10^9$。

输出格式

对每组输入，输出其运算结果。

4
1 2 3 4
2 1 3 5
3 0 4 7
19871031 20240529 12345678 87654321

2
3
2
84209721

斐波那契数列从零开始前十项：$0,1,1,2,3,5,8,13,21,34,55$。

在取模前：

• 对于输入1：$f_2+f_3+f_4=1+2+3=6$；
• 对于输入2：$f_1+f_3+f_5=1+2+5=8$；
• 对于输入3：$f_0+f_3+f_6+f_9=0+2+8+34=44$。