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

输入格式
第一行一个数字 $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 \leq 123, a,n,d< p = 1234567891$。