#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 ;
C.A[0][1] = (M.A[0][0] * N.A[0][1] + M.A[0][1] * N.A[1][1]) % MOD ;
C.A[1][0] = (M.A[1][0] * N.A[0][0] + M.A[1][1] * N.A[1][0]) % MOD ;
C.A[1][1] = (M.A[1][0] * N.A[0][1] + M.A[1][1] * N.A[1][1]) % MOD ;
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+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGNtYXRoPgojZGVmaW5lIE1PRCAxMDAwMDAwMDA3CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpzdHJ1Y3QgTWF0cml4CnsKCQlsb25nIGxvbmcgaW50IEFbMl1bMl0gOwoKfTsKCk1hdHJpeCBtdWx0KE1hdHJpeCBNLCBNYXRyaXggTil7CgoKCU1hdHJpeCBDIAk7CgoJQy5BWzBdWzBdID0gKE0uQVswXVswXSAqIE4uQVswXVswXSArIE0uQVswXVsxXSAqIE4uQVsxXVswXSkJJSBNT0QgICA7ICAgICAgICAgICAKCUMuQVswXVsxXSA9IChNLkFbMF1bMF0gKiBOLkFbMF1bMV0gKyBNLkFbMF1bMV0gKiBOLkFbMV1bMV0pICUgTU9ECTsKCUMuQVsxXVswXSA9IChNLkFbMV1bMF0gKiBOLkFbMF1bMF0gKyBNLkFbMV1bMV0gKiBOLkFbMV1bMF0pICUgTU9ECTsgIAoJQy5BWzFdWzFdID0gKE0uQVsxXVswXSAqIE4uQVswXVsxXSArIE0uQVsxXVsxXSAqIE4uQVsxXVsxXSkgJSBNT0QJOwoKCXJldHVybiBDOwoKfQoKTWF0cml4IEJpbl9FeHAoTWF0cml4IEEsIGludCBuKQl7CgoJaWYgKG4gPT0gMSkKCQlyZXR1cm4gQQk7CgoJTWF0cml4IGludGVyID0gQmluX0V4cChBLCBuIC8gMikJOwoKCWlmIChuICUgMikKCQlyZXR1cm4gbXVsdChBLCBtdWx0KGludGVyLCBpbnRlcikpOwoJcmV0dXJuIG11bHQoaW50ZXIsIGludGVyKQk7Cn0KCmxvbmcgbG9uZyBpbnQgYmluX2V4cChsb25nIGxvbmcgaW50IGJhc2UsIGxvbmcgbG9uZyBpbnQgZXhwKXsKCglpZiAoZXhwID09IDApCgkJcmV0dXJuIDE7CglpZiAoZXhwID09IDEpCgkJcmV0dXJuIGJhc2UJOwoKCWxvbmcgbG9uZyBpbnQgaW50ZXIgPSBiaW5fZXhwKGJhc2UsIGV4cCAvIDIpCTsKCWlmIChleHAgJSAyKQoJCXJldHVybiAoYmFzZSAlIE1PRCAgKiAoaW50ZXIgKiBpbnRlcikgJSBNT0QpJU1PRDsKCXJldHVybiAoaW50ZXIgKiBpbnRlcikgJSBNT0Q7Cgp9CgoKaW50IG1haW4oKXsKCglpbnQgdCwgRjAsIEYxLCBuLCBLIDsKCU1hdHJpeCB0cmFucyA7CglzY2FuZigiJWQiLCAmdCkJOwoJd2hpbGUodC0tKXsKCgkJc2NhbmYoIiVkICVkICVkICVkIiwgJkYwLCAmRjEsICZuLCAmSyk7CgoJCXRyYW5zLkFbMF1bMF0gPSBLOyB0cmFucy5BWzBdWzFdID0gSyA7CgkJdHJhbnMuQVsxXVswXSA9IDE7IHRyYW5zLkFbMV1bMV0gPSAwIDsKCgkJaWYgKG4gPT0gMSl7CgkJCXByaW50ZigiJWRcbiIsIEYxKTsKCQkJY29udGludWU7CgkJfQoKCQlpZiAobiA9PSAwKXsKCQkJcHJpbnRmKCIlZFxuIiwgRjApOwoJCQljb250aW51ZTsKCQl9CgkJCgkJTWF0cml4IGFucyA9IEJpbl9FeHAodHJhbnMsIG4tMSkJOyAKCgkJaW50IHNvbCA9IChiaW5fZXhwKEYxLCBhbnMuQVswXVswXSkgJSBNT0QgKiBiaW5fZXhwKEYwLCBhbnMuQVswXVsxXSklTU9EKSVNT0QJOwoJCXByaW50ZigiJWRcbiIsIHNvbCk7Cgl9CgoJcmV0dXJuIDAJOwp9CiAgICAK