F. Find a Square
time limit per test
6 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Frank likes square numbers. That is numbers, which are the product of some integer with itself. Also Frank likes quadratic polynomials. He even has his favorite one: $$$p(x) = a \cdot x^2 + b \cdot x + c$$$.

This morning Frank evaluated his favorite quadratic polynomial for $$$n$$$ consecutive integer arguments starting from $$$0$$$ and multiplied all the numbers he got.

If the resulting product is a square, his day is just perfect, but that might be not the case. So he asks you to find the largest square number which is a divisor of the resulting product.

Input

The only line of the input contains 4 integers $$$a, b, c, n$$$ ($$$1 \le a,b,c,n \le 600\,000$$$).

Output

Find the largest square divisor of $$$\prod\limits_{i=0}^{n-1}{p(i)}$$$. As this number could be very large, output a single integer — its remainder modulo $$$10^9+7$$$.

Examples
Input
1 1 1 10
Output
74529
Input
1 2 1 10
Output
189347824
Note

In the first example, the product is equal to $$$1\cdot 3\cdot 7\cdot 13\cdot 21\cdot 31\cdot 43\cdot 57\cdot 73\cdot 91 = 2893684641939 = 38826291 \cdot 273^2$$$.