#include<stdio.h>
#include<math.h>
long long int func(long long int n,long long int k,long long int f0,long long int f1);
int main()
{int t;
long long int n,k,f0,f1,ans,ans1;
scanf("%d",&t);
while(t--)
{
scanf("%lld%lld%lld%lld",&f0,&f1,&n,&k);
ans=func(n,k,f0,f1);
ans1=ans%1000000007;
printf("%lld\n",ans1);
}
return 0;
}
long long int func(long long int n,long long int k,long long int f0,long long int f1)
{if(n==0)
return f0;
if(n==1)
return f1;
return pow((func(n-1,k,f0,f1)*func(n-2,k,f0,f1)),k);
}

I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8bWF0aC5oPgpsb25nIGxvbmcgaW50IGZ1bmMobG9uZyBsb25nIGludCBuLGxvbmcgbG9uZyBpbnQgayxsb25nIGxvbmcgaW50IGYwLGxvbmcgbG9uZyBpbnQgZjEpOwppbnQgbWFpbigpCntpbnQgdDsKbG9uZyBsb25nIGludCBuLGssZjAsZjEsYW5zLGFuczE7CnNjYW5mKCIlZCIsJnQpOwp3aGlsZSh0LS0pCnsKc2NhbmYoIiVsbGQlbGxkJWxsZCVsbGQiLCZmMCwmZjEsJm4sJmspOwphbnM9ZnVuYyhuLGssZjAsZjEpOwphbnMxPWFucyUxMDAwMDAwMDA3OwpwcmludGYoIiVsbGRcbiIsYW5zMSk7Cn0KcmV0dXJuIDA7Cn0KbG9uZyBsb25nIGludCBmdW5jKGxvbmcgbG9uZyBpbnQgbixsb25nIGxvbmcgaW50IGssbG9uZyBsb25nIGludCBmMCxsb25nIGxvbmcgaW50IGYxKQp7aWYobj09MCkKcmV0dXJuIGYwOwppZihuPT0xKQpyZXR1cm4gZjE7CnJldHVybiBwb3coKGZ1bmMobi0xLGssZjAsZjEpKmZ1bmMobi0yLGssZjAsZjEpKSxrKTsKfQ==

MQoxIDEgMiAxCg==

1
1 1 2 1