505017 - XLkxc

【题目描述】XLkxc(xlkxc)

给定 k,a,n,d,p,有f(i)=1k+2k+3k+...+ik,g(x)=f(1)+f(2)+f(3)+...+f(x)。 求(g(a)+g(a+d)+g(a+2d)+......+g(a+nd)) mod p的值。

输入

第一行为一个整数T,表示测试数据组数(保证保证小于6)。 随后每行四个整数k,a,n,d(1≤k≤123,0≤a,n,d≤123456789,p=1 234567891)。

输出

每行输出一组测试数据的答案。

样例

输入

2
1 1 1 1
1 1 1 1

输出

5
5
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题