tyvj 1858 XLkxc

时间限制:20s      空间限制:128MB

题目描述

神犇LYD虐完HEOI之后给傻×XLk出了一题:
SHY是某国的公主,平时的一大爱好是读诗...(中间略)...结果mod p就可以了

简明题意
给定 k,a,n,d,p
f(i)=1^k+2^k+3^k+......+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

对于所有数据
1<=k<=123
0<=a,n,d<=123456789
p==1234567891


输入格式

第一行数据组数,(保证小于6)
以下每行四个整数 k,a,n,d


输出格式

每行一个结果。


样例输入

5
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

提示

没有写明提示


题目来源

没有写明来源