给定 $k,a,n,d,p$

$f(i)=1^k+2^k+3^k+ \dots +i^k$

$g(x)=f(1)+f(2)+f(3)+⋯+f(x)$

求 $(g(a)+g(a+d)+g(a+2d)+......+g(a+nd)) \mod p$

输入格式

有多组数据。 第一行输入数据组数 T； 以下 T 行，每行四个整数，代表这组数据中的 k,a,n,d。

输出格式

共 T 行，每行一个整数，表示计算出的结果。

输入数据 1

5
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

输出数据 1

5
5
5
5
5

数据范围

对于 $100$ 的数据：$1≤k≤123,0≤a,n,d≤123456789,p=1234567891$