407804: GYM102896 F Find a Square

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.

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

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$$$.

1 1 1 10

74529

1 2 1 10

189347824

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$$$.