3633: 一起自习的日子
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：
题目描述
求
输入
多组数据。第一行，一个整数 T，表示数据组数；
接下来 T 行，每行 4 个正整数 k, a, n, d，含义如上所示。
输出
输出一行，一个整数，表示答案，输出结果请对 1234567891 取模。
样例输入 复制
4
1 51 49 1
1 52 56 1
1 53 53 1
1 51 56 1样例输出 复制
4128450
5672754
5222196
5480360提示
存在 30% 的数据，有 1 ≤ k ≤ 150；
存在 40% 的数据，有 a + nd ≤ 106；
对于 100% 的数据，有 1 ≤ T ≤ 4, 1 ≤ k ≤ 3000, 1 ≤ a, n, d < 1234567891。