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）。

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