题目描述

求 $\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$。