U283466 多项式求和 Lite Version

因为清华2017年考研的《多项式求和》把大伙都做自闭了，所以整个简单点的（迫真）。

已知 $f(x)=\sum_{i=1}^x i^k,g(x)=\sum_{i=1}^x f(i)$ 。 给定函数 $S(n)=\sum_{i=0}^n g(a + id)$ 。 在给定 $k,a,n,d$ 的情况下，求解 $S(n)\bmod 1234567891$。 其中 $1234567891$ 是一个质数。

每个测试点有多组数据。 第一行为数据组数 $T(T\le 5)$ 接下来 $T$ 行，每行 $4$ 个数，分别为 $k,a,n,d$。

每行输出一个自然数，表示 $S(n)\bmod 1234567891$ 。

对于 $40\%$ 的数据有 : $k\le 123$ 。 对于 $100\%$ 的数据有 : $k\le 3000, a,n,d