#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define mod 1000000007LL
#define ll long long
#define pii pair<int,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define beg begin()
#define sz size()
#define itr iterator
#define piii pair<int, pii >
ll md[100011];
ll solve (ll a, ll b, ll m)
{
ll ans1 = 100*m;
ll n = (ll) sqrt (m + .0) + 1;
ll an = 1;
for (ll i=0; i<n; ++i)
an = (an * a) % m;
map<ll,ll> vals;
for (ll i=1, cur=an; i<=n; ++i) {
if (!vals.count(cur))
vals[cur] = i;
cur = (cur * an) % m;
}
for (ll i=0, cur=b; i<=n; ++i) {
if (vals.count(cur)) {
ll ans = vals[cur] * n - i;
if (ans < m)
ans1 = min(ans,ans1);
}
cur = (cur * a) % m;
}
if(ans1 != 100*m)
return ans1;
else
return -1;
}
ll solve1 (ll a, ll b, ll m)
{
ll ans1 = 100*m;
ll n = (ll) sqrt (m + .0) + 1;
ll an = 1;
for (ll i=0; i<n; ++i)
an = (an * a) % m;
map<ll,ll> vals;
for (ll i=1, cur=an; i<=n; ++i) {
if (!vals.count(cur))
vals[cur] = i;
cur = (cur * an) % m;
}
for (ll i=0, cur=b; i<=n; ++i) {
if (vals.count(cur)) {
ll ans = vals[cur] * n - i;
if (ans < m&&ans!=0LL)
ans1 = min(ans,ans1);
}
cur = (cur * a) % m;
}
if(ans1 != 100*m)
return ans1;
else
return -1;
}
int main()
{
int t,i;
scanf("%d",&t);
while(t--)
{
ll a,c,m,k;
scanf("%lld %lld %lld %lld",&a,&c,&m,&k);
ll len=solve1(a,1LL,m);
ll p=solve(a,c,m);
if(p==-1)
{
printf("0\n");
continue;
}
ll ans=(k*(k-1LL))/2LL;
ans%=mod;
ans=(ans*len)%mod;
ans=(ans+(k*p))%mod;
printf("%lld\n",ans);
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBmIGZpcnN0CiNkZWZpbmUgcyBzZWNvbmQKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBtb2QgMTAwMDAwMDAwN0xMCiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgcGlpIHBhaXI8aW50LGludD4KI2RlZmluZSBwaWwgcGFpcjxpbnQsbGw+CiNkZWZpbmUgcGxsIHBhaXI8bGwsbGw+CiNkZWZpbmUgcGxpIHBhaXI8bGwsaW50PgojZGVmaW5lIGJlZyBiZWdpbigpCiNkZWZpbmUgc3ogc2l6ZSgpCiNkZWZpbmUgaXRyIGl0ZXJhdG9yCiNkZWZpbmUgcGlpaSBwYWlyPGludCwgcGlpID4KbGwgbWRbMTAwMDExXTsKbGwgc29sdmUgKGxsIGEsIGxsIGIsIGxsIG0pCiB7CiAgICBsbCBhbnMxID0gMTAwKm07CiAgICBsbCBuID0gKGxsKSBzcXJ0IChtICsgLjApICsgMTsKIAogICAgbGwgYW4gPSAxOwogICAgZm9yIChsbCBpPTA7IGk8bjsgKytpKQogICAgICAgIGFuID0gKGFuICogYSkgJSBtOwogCiAgICBtYXA8bGwsbGw+IHZhbHM7CiAgICBmb3IgKGxsIGk9MSwgY3VyPWFuOyBpPD1uOyArK2kpIHsKICAgICAgICBpZiAoIXZhbHMuY291bnQoY3VyKSkKICAgICAgICAgICAgdmFsc1tjdXJdID0gaTsKICAgICAgICBjdXIgPSAoY3VyICogYW4pICUgbTsKICAgIH0KIAogICAgZm9yIChsbCBpPTAsIGN1cj1iOyBpPD1uOyArK2kpIHsKICAgICAgICBpZiAodmFscy5jb3VudChjdXIpKSB7CiAgICAgICAgICAgIGxsIGFucyA9IHZhbHNbY3VyXSAqIG4gLSBpOwogICAgICAgICAgICBpZiAoYW5zIDwgbSkKICAgICAgICAgICAgICAgIGFuczEgPSBtaW4oYW5zLGFuczEpOwogICAgICAgIH0KICAgICAgICBjdXIgPSAoY3VyICogYSkgJSBtOwogICAgfQogICAgaWYoYW5zMSAhPSAxMDAqbSkKICAgICAgICByZXR1cm4gYW5zMTsKICAgIGVsc2UKICAgICAgICByZXR1cm4gLTE7Cn0KbGwgc29sdmUxIChsbCBhLCBsbCBiLCBsbCBtKQogewogICAgbGwgYW5zMSA9IDEwMCptOwogICAgbGwgbiA9IChsbCkgc3FydCAobSArIC4wKSArIDE7CiAKICAgIGxsIGFuID0gMTsKICAgIGZvciAobGwgaT0wOyBpPG47ICsraSkKICAgICAgICBhbiA9IChhbiAqIGEpICUgbTsKIAogICAgbWFwPGxsLGxsPiB2YWxzOwogICAgZm9yIChsbCBpPTEsIGN1cj1hbjsgaTw9bjsgKytpKSB7CiAgICAgICAgaWYgKCF2YWxzLmNvdW50KGN1cikpCiAgICAgICAgICAgIHZhbHNbY3VyXSA9IGk7CiAgICAgICAgY3VyID0gKGN1ciAqIGFuKSAlIG07CiAgICB9CiAKICAgIGZvciAobGwgaT0wLCBjdXI9YjsgaTw9bjsgKytpKSB7CiAgICAgICAgaWYgKHZhbHMuY291bnQoY3VyKSkgewogICAgICAgICAgICBsbCBhbnMgPSB2YWxzW2N1cl0gKiBuIC0gaTsKICAgICAgICAgICAgaWYgKGFucyA8IG0mJmFucyE9MExMKQogICAgICAgICAgICAgICAgYW5zMSA9IG1pbihhbnMsYW5zMSk7CiAgICAgICAgfQogICAgICAgIGN1ciA9IChjdXIgKiBhKSAlIG07CiAgICB9CiAgICBpZihhbnMxICE9IDEwMCptKQogICAgICAgIHJldHVybiBhbnMxOwogICAgZWxzZQogICAgICAgIHJldHVybiAtMTsKfQppbnQgbWFpbigpCnsKICAgIGludCB0LGk7CiAgICBzY2FuZigiJWQiLCZ0KTsKICAgIHdoaWxlKHQtLSkKICAgIHsKICAgICAgICBsbCBhLGMsbSxrOwogICAgICAgIHNjYW5mKCIlbGxkICVsbGQgJWxsZCAlbGxkIiwmYSwmYywmbSwmayk7CgogICAgICAgIGxsIGxlbj1zb2x2ZTEoYSwxTEwsbSk7CgogICAgICAgIGxsIHA9c29sdmUoYSxjLG0pOwoKICAgICAgICBpZihwPT0tMSkKICAgICAgICB7CiAgICAgICAgICAgIHByaW50ZigiMFxuIik7CiAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgIH0KCiAgICAgICAgbGwgYW5zPShrKihrLTFMTCkpLzJMTDsKICAgICAgICBhbnMlPW1vZDsKICAgICAgICBhbnM9KGFucypsZW4pJW1vZDsKICAgICAgICBhbnM9KGFucysoaypwKSklbW9kOwogICAgICAgIHByaW50ZigiJWxsZFxuIixhbnMpOwogICAgfQogICAgcmV0dXJuIDA7Cn0KIA==