2529: #6024. XLkxc

求 ${\sum }_{i=0}^n{\sum }_{j=1}^{a+i\cdot d}{\sum }_{l=1}^j{l}^{k}modp$。

输入格式

第一行一个数字 $T$ ，表示数据的组数。

接下来每行四个整数，表示 $k$，$a$，$n$，$d$ 。

输出格式

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

样例

样例输入

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\%$ 的数据，$k\le 123,a,n,d<p=123456791$。