#150. XLkxc

XLkxc

题目描述

求 $\sum_{i=0}^n\sum_{j=1}^{a+i\cdot d}\sum_{l=1}^jl^k \bmod p$。

输入格式

第一行一个数字 TT ,表示数据的组数。

接下来每行四个整数,表示 kkaanndd

输出格式

每行一个整数,表示答案 。

5
5 7 5 7
6 8 6 8
70 35 26 72
90 18 32 64
123 321 123 321
150448172
1121208122
276955429
1024718000
585044920

数据范围与提示

对于 100% 100\% 的数据,k123,a,n,d<p=1234567891 k \leq 123, a,n,d< p = 1234567891