求 ∑ni=0∑a+i⋅dj=1∑jl=1lkmodp。
第一行一个数字 TTT ，表示数据的组数。
接下来每行四个整数，表示 kkk，aaa，nnn，ddd 。
每行一个整数，表示答案 。
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\% 100% 的数据，k≤123,a,n,d<p=123456791 k \leq 123, a,n,d< p = 123456791k≤123,a,n,d<p=123456791。