SP11777 SEQAGAIN - Easy Sequence!

Your task is to find the n $ ^{th} $ term of the following sequence : F(n) = \[F(n-1)\*F(n-2)\] $ ^{K} $ for n>1 F(0), F(1), n and K will be provided as input. Modulus for all calculations is 1000000007. You should print the answer modulo 1000000007 i.e. F(n)%1000000007

Input starts with a line containing an integer T Each test case consists of four space separated integers : F(0), F(1), n and K.

T lines containing one integer each, corresponding to the answers for the T test cases.