# 题意

• $1 \leq T \leq 20$
• $0 \leq A, B, C, D \leq 10^9$
• $1 \leq P, n \leq 10^9$

# 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll modulo = (ll) 1e9 + 7;

class matrix{
public:
ll s[3][3];

matrix(){
memset(s, 0, sizeof(s));
}
matrix(ll Fn, ll Fn1, ll E) {
s[0][0] = Fn;
s[0][1] = Fn1;
s[0][2] = E;
s[1][0] = s[1][1] = s[1][2] = 0;
s[2][0] = s[2][1] = s[2][2] = 0;
}
matrix(ll C, ll D) {
s[0][0] = D;
s[1][0] = C;
s[0][1] = s[2][0] = s[2][2] = 1;
s[0][2] = s[1][1] = s[1][2] = s[2][1] = 0;
}
};

matrix mul(matrix &a, matrix &b) {
matrix ret;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
for (int k = 0; k < 3; ++k) {
ret.s[i][j] = (ret.s[i][j] + a.s[i][k] * b.s[k][j]) % modulo;
}
}
}
return ret;
}

ll A = 0, B = 0, C = 0, D = 0, P = 0, n = 0;

void xmul(ll &Fn, ll &Fn1, ll E, ll t) {
matrix ret(Fn, Fn1, E);
matrix b(C, D);
while (t) {
if (t & 1) {
ret = mul(ret, b);
}
b = mul(b, b);
t >>= 1;
}
Fn = ret.s[0][0];
Fn1 = ret.s[0][1];
}

ll solve() {
if (n == 1) return A;
if (n == 2) return B;
ll Fn1 = A, Fn = B, nex = 0, PN = 0;
matrix res;
for (ll i = 3; i <= n; ) {
PN = P / i;
if (PN == 0) {
nex = n;
} else {
nex = min(n, P / PN);
}
xmul(Fn, Fn1, PN, nex - i + 1);
i = nex + 1;
}
return Fn;
}

int main() {
int T = 0;
scanf("%d", &T);
while (T--) {
scanf("%lld%lld%lld%lld%lld%lld", &A, &B, &C, &D, &P, &n);
printf("%lld\n", solve());
}
}