1381: #6024. XLkxc
[Creator : ]
Description
求$\sum_{i=0}^n \sum_{j=1}^{a+i\cdot d} \sum^{j}_{l=1} l^k\ \bmod p$。
Input
第一行一个数字 T ，表示数据的组数。
接下来每行四个整数，表示 k,a,n,d。
接下来每行四个整数，表示 k,a,n,d。
Output
每行一个整数，表示答案 。
Constraints
对于 $100\%$ 的数据，$k \leq 123,\ a,n,d< p = 123456791$。
Sample 1 Input
5
5 7 5 7
6 8 6 8
70 35 26 72
90 18 32 64
123 321 123 321
Sample 1 Output
150448172
1121208122
276955429
1024718000
585044920