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

제한

힌트

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