Problem Description

There is a function $ f(n) = (a+\sqrt{b})^n + (a-\sqrt{b})^n $. a and b are integers $(1 \leq a,b \leq 1,000,000)$.
Maybe the function looks complex but it is actually an integer.The question is to calculate $ f(x^y)$.The answer can be
very large,so just output the answer mod $1,000,000,007$.

Input

There are multiple test cases. The first line of input contains an integer $T (1\leq T\leq 200)$ indicating the number of test cases. For each test case:

One line contains four integers $a,b$ $\ (1 \leq a,b \leq 1,000,000)$, $\ x(1\leq x \leq 50), y(1\leq y \leq 10^{18})$.

Output

For each test case, output one integer.

3
3 5 1 1
3 5 2 1
1 1 49 99999

6
28
160106184