#include<bits/stdc++.h>
#include <queue>
typedef long long int ll;
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t, n;
cin>>t;
long long int sum = 0, a, b, c, d, med, z;
while (t > 0) {
t--;
priority_queue <ll> max;
priority_queue <ll, vector<ll>, greater<ll> > min;
cin>>a>>b>>c>>n;
d = b;
sum = 1;
max.push(1l);
b += d;
for(int i = 2; i <= n; i++) {
int mxs = max.size(), mis = min.size();
ll mxp = max.top();
ll mip = -1l;
if(mis != 0) mip = min.top();
med = mxp;
z = ((a * med) + b + c) % 1000000007;
b += d;
sum += z;
if(mxs == mis) {
if(mis == 0) max.push(z);
else if(mxp <= z && mip >= z) {
max.push(z);
}
else if(mip < z) {
max.push(min.top());
min.pop();
min.push(z);
}
else {
max.push(z);
}
}
else {
if(mis == 0) {
if(mxp <= z) min.push(z);
else {
min.push(max.top());
max.pop();
max.push(z);
}
}
else if(mxp <= z) {
min.push(z);
}
else {
min.push(max.top());
max.pop();
max.push(z);
}
}
}
cout<<sum<<endl;
}
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4gCiNpbmNsdWRlIDxxdWV1ZT4KdHlwZWRlZiBsb25nIGxvbmcgaW50IGxsOwp1c2luZyBuYW1lc3BhY2Ugc3RkOyAKCgppbnQgbWFpbigpIHsgCglpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGNpbi50aWUoTlVMTCk7CglpbnQgdCwgbjsKCWNpbj4+dDsKCWxvbmcgbG9uZyBpbnQgc3VtID0gMCwgYSwgYiwgYywgZCwgbWVkLCB6OwoJd2hpbGUgKHQgPiAwKSB7CgkJdC0tOwoJCXByaW9yaXR5X3F1ZXVlIDxsbD4gbWF4OwoJCXByaW9yaXR5X3F1ZXVlIDxsbCwgdmVjdG9yPGxsPiwgZ3JlYXRlcjxsbD4gPiBtaW47CgkJY2luPj5hPj5iPj5jPj5uOwoJCWQgPSBiOwoJCXN1bSA9IDE7CgkJbWF4LnB1c2goMWwpOwoJCWIgKz0gZDsKCQlmb3IoaW50IGkgPSAyOyBpIDw9IG47IGkrKykgewoJCQlpbnQgbXhzID0gbWF4LnNpemUoKSwgbWlzID0gbWluLnNpemUoKTsKCQkJbGwgbXhwID0gbWF4LnRvcCgpOyAKCQkJbGwgbWlwID0gLTFsOwoJCQlpZihtaXMgIT0gMCkgbWlwID0gbWluLnRvcCgpOwoJCQltZWQgPSBteHA7CgkJCXogPSAoKGEgKiBtZWQpICsgYiArIGMpICUgMTAwMDAwMDAwNzsKCQkJYiArPSBkOwoJCQlzdW0gKz0gejsKCQkJaWYobXhzID09IG1pcykgewoJCQkJaWYobWlzID09IDApIG1heC5wdXNoKHopOwoJCQkJZWxzZSBpZihteHAgPD0geiAmJiBtaXAgPj0geikgewoJCQkJCW1heC5wdXNoKHopOwoJCQkJfQoJCQkJZWxzZSBpZihtaXAgPCB6KSB7CgkJCQkJbWF4LnB1c2gobWluLnRvcCgpKTsKCQkJCQltaW4ucG9wKCk7CgkJCQkJbWluLnB1c2goeik7CgkJCQl9CgkJCQllbHNlIHsKCQkJCQltYXgucHVzaCh6KTsKCQkJCX0KCQkJfQoJCQllbHNlIHsKCQkJCWlmKG1pcyA9PSAwKSB7CgkJCQkJaWYobXhwIDw9IHopIG1pbi5wdXNoKHopOwoJCQkJCWVsc2UgewoJCQkJCQltaW4ucHVzaChtYXgudG9wKCkpOwoJCQkJCQltYXgucG9wKCk7CgkJCQkJCW1heC5wdXNoKHopOwoJCQkJCX0KCQkJCX0KCQkJCWVsc2UgaWYobXhwIDw9IHopIHsKCQkJCQltaW4ucHVzaCh6KTsKCQkJCX0KCQkJCWVsc2UgewoJCQkJCW1pbi5wdXNoKG1heC50b3AoKSk7CgkJCQkJbWF4LnBvcCgpOwoJCQkJCW1heC5wdXNoKHopOwoJCQkJfQoJCQl9CgkJfQoJCWNvdXQ8PHN1bTw8ZW5kbDsKCX0KfSAK