定义函数 $ f(n) = (a+\sqrt{b})^n + (a-\sqrt{b})^n $，其中$a$和$b$都是整数。$(1 \leq a,b \leq 1,000,000)$ 这个函数包含了复杂运算，但是可以证明它的值是整数。
在这个问题里，任务是计算 $ f(x^y)$。答案可能会很大，所以只需输出答案对$1,000,000,007$的模。
输入包含多组数据. 第一行有一个整数$T (1\leq T\leq 15)$, 表示测试数据的组数. 对于每组数据:
一行包含四个整数 $a,b\ (1 \leq a,b \leq 1,000,000),\ x(1\leq x \leq 50),\ y(1\leq y \leq 10^{18})$。
对于每组数据，输出一个整数。
3 3 5 1 1 3 5 2 1 1 1 49 99999
6 28 160106184