#include <stdio.h>
#include <iostream>
#include <cmath>
#define MOD 1000000007
using namespace std;
struct Matrix
{
long long int A[2][2] ;
};
Matrix mult(Matrix M, Matrix N){
Matrix C ;
C.A[0][0] = (M.A[0][0] * N.A[0][0] + M.A[0][1] * N.A[1][0]) % (MOD-1) ;
C.A[0][1] = (M.A[0][0] * N.A[0][1] + M.A[0][1] * N.A[1][1]) % (MOD-1) ;
C.A[1][0] = (M.A[1][0] * N.A[0][0] + M.A[1][1] * N.A[1][0]) % (MOD-1) ;
C.A[1][1] = (M.A[1][0] * N.A[0][1] + M.A[1][1] * N.A[1][1]) % (MOD-1) ;
return C;
}
Matrix Bin_Exp(Matrix A, int n) {
if (n == 1)
return A ;
Matrix inter = Bin_Exp(A, n / 2) ;
if (n % 2)
return mult(A, mult(inter, inter));
return mult(inter, inter) ;
}
long long int bin_exp(long long int base, long long int exp){
if (exp == 0)
return 1;
if (exp == 1)
return base ;
long long int inter = bin_exp(base, exp / 2) ;
if (exp % 2)
return (base % MOD * (inter * inter) % MOD)%MOD;
return (inter * inter) % MOD;
}
int main(){
int t, F0, F1, n, K ;
Matrix trans ;
scanf("%d", &t) ;
while(t--){
scanf("%d %d %d %d", &F0, &F1, &n, &K);
trans.A[0][0] = K; trans.A[0][1] = K ;
trans.A[1][0] = 1; trans.A[1][1] = 0 ;
if (n == 1){
printf("%d\n", F1);
continue;
}
if (n == 0){
printf("%d\n", F0);
continue;
}
Matrix ans = Bin_Exp(trans, n-1) ;
int sol = (bin_exp(F1, ans.A[0][0]) % MOD * bin_exp(F0, ans.A[0][1])%MOD)%MOD ;
printf("%d\n", sol);
}
return 0 ;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGNtYXRoPgojZGVmaW5lIE1PRCAxMDAwMDAwMDA3CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpzdHJ1Y3QgTWF0cml4CnsKCQlsb25nIGxvbmcgaW50IEFbMl1bMl0gOwoKfTsKCk1hdHJpeCBtdWx0KE1hdHJpeCBNLCBNYXRyaXggTil7CgoKCU1hdHJpeCBDIAk7CgoJQy5BWzBdWzBdID0gKE0uQVswXVswXSAqIE4uQVswXVswXSArIE0uQVswXVsxXSAqIE4uQVsxXVswXSkJJSAoTU9ELTEpICAgOyAgICAgICAgICAgCglDLkFbMF1bMV0gPSAoTS5BWzBdWzBdICogTi5BWzBdWzFdICsgTS5BWzBdWzFdICogTi5BWzFdWzFdKSAlIChNT0QtMSkJOwoJQy5BWzFdWzBdID0gKE0uQVsxXVswXSAqIE4uQVswXVswXSArIE0uQVsxXVsxXSAqIE4uQVsxXVswXSkgJSAoTU9ELTEpCTsgIAoJQy5BWzFdWzFdID0gKE0uQVsxXVswXSAqIE4uQVswXVsxXSArIE0uQVsxXVsxXSAqIE4uQVsxXVsxXSkgJSAoTU9ELTEpCTsKCglyZXR1cm4gQzsKCn0KCk1hdHJpeCBCaW5fRXhwKE1hdHJpeCBBLCBpbnQgbikJewoKCWlmIChuID09IDEpCgkJcmV0dXJuIEEJOwoKCU1hdHJpeCBpbnRlciA9IEJpbl9FeHAoQSwgbiAvIDIpCTsKCglpZiAobiAlIDIpCgkJcmV0dXJuIG11bHQoQSwgbXVsdChpbnRlciwgaW50ZXIpKTsKCXJldHVybiBtdWx0KGludGVyLCBpbnRlcikJOwp9Cgpsb25nIGxvbmcgaW50IGJpbl9leHAobG9uZyBsb25nIGludCBiYXNlLCBsb25nIGxvbmcgaW50IGV4cCl7CgoJaWYgKGV4cCA9PSAwKQoJCXJldHVybiAxOwoJaWYgKGV4cCA9PSAxKQoJCXJldHVybiBiYXNlCTsKCglsb25nIGxvbmcgaW50IGludGVyID0gYmluX2V4cChiYXNlLCBleHAgLyAyKQk7CglpZiAoZXhwICUgMikKCQlyZXR1cm4gKGJhc2UgJSBNT0QgICogKGludGVyICogaW50ZXIpICUgTU9EKSVNT0Q7CglyZXR1cm4gKGludGVyICogaW50ZXIpICUgTU9EOwoKfQoKCmludCBtYWluKCl7CgoJaW50IHQsIEYwLCBGMSwgbiwgSyA7CglNYXRyaXggdHJhbnMgOwoJc2NhbmYoIiVkIiwgJnQpCTsKCXdoaWxlKHQtLSl7CgoJCXNjYW5mKCIlZCAlZCAlZCAlZCIsICZGMCwgJkYxLCAmbiwgJkspOwoKCQl0cmFucy5BWzBdWzBdID0gSzsgdHJhbnMuQVswXVsxXSA9IEsgOwoJCXRyYW5zLkFbMV1bMF0gPSAxOyB0cmFucy5BWzFdWzFdID0gMCA7CgoJCWlmIChuID09IDEpewoJCQlwcmludGYoIiVkXG4iLCBGMSk7CgkJCWNvbnRpbnVlOwoJCX0KCgkJaWYgKG4gPT0gMCl7CgkJCXByaW50ZigiJWRcbiIsIEYwKTsKCQkJY29udGludWU7CgkJfQoJCQoJCU1hdHJpeCBhbnMgPSBCaW5fRXhwKHRyYW5zLCBuLTEpCTsgCgoJCWludCBzb2wgPSAoYmluX2V4cChGMSwgYW5zLkFbMF1bMF0pICUgTU9EICogYmluX2V4cChGMCwgYW5zLkFbMF1bMV0pJU1PRCklTU9ECTsKCQlwcmludGYoIiVkXG4iLCBzb2wpOwoJfQoKCXJldHVybiAwCTsKfQogICAgCg==